【笔记】简单入门「堆」
# 简单入门「堆」==文章内容来自于对**王争**老师[《数据结构与算法之美》](https://time.geekbang.org/column/article/69913)栏的学习整理。==
**堆是一种特殊的完全二叉树（也称：二叉堆）。每一个节点都大于等于 / 小于等于它的子节点**。
入门要求：
1. 熟悉数组
2. 了解链表
3. 熟悉排序的基础概念
4. 理解什么是二叉树
## 基本概念
**大顶堆**，**完全二叉树** 中的每一个结点都大于等于它的子节点。
**小顶堆**，**完全二叉树** 每一个结点都小于等于它的子节点。
通常用数组来表示 **堆**，方便 **堆** 中数据的读取。
### 实现一个堆
浪费 heap 的空间则所有的左子节点都可以表示为 2*i 、右子节点都可以表示为 2*i+1.若不浪费 1 个空间，则左子节点都表示为 2*i+1，右子节点表示为 2*i+2（ i 代表父节点数组索引），需要多做 1 次加法运算，在频繁的读取操作中会浪费更多的运算内存。
```java
class HeapTest {
private int[] heap; // 定义数组存储堆的数据,数组从 1 开始
private int length; // 定义堆的大小
private int count; // 堆中已有数据个数
public HeapTest(int capacity) { // capacity 表示数组容量
heap = new int;
length = capacity;
count = 0;
}
}
```
## 堆化
<font color="#FF0000">以下代码皆以大顶堆为例</font>
**堆** 通常应用于动态的数据存储，所以有频繁的数据更新。当一个新数据放入堆中时，我们需要让堆满足：所有节点都大于或等于上子节点这一条件。而这一对堆内数据进行整理的过程被称做「**堆化**」。
**堆化**，分为两种：
- **自顶向下**，即从堆顶（**二叉树的根节点**）开始一层层的向下整理堆中数据。通常应用于：**移除堆顶元素**。
- **自底向上**，即从堆中最后一个数据开始和 **父节点** 比较并进行有必要的交换。通常用于：**向堆中插入一个新元素**、**建堆**。
### 插入元素以及移除堆顶元素
堆中**插入元素**（自底向上）思路：
- 首先看堆中是否还能够存储插入元素。是则 **默认将元素放置堆尾**。
- 在插入点存在父节点的前提下比较是否大于父节点，是则交换两数的值。
注意：因为所有的左子树索引值都为 2*i、右子树都为 2*i+1，则父节点索引值为 i，即 子节点索引值/ 2.
```java
public void insert(int num) {
if (count >= length) {
return;
}
count++;
heap = num;
int i = count;
while (i / 2 > 0 && heap > heap) { // 判断是否存在父节点且小于插入元素
swap(heap, i, i / 2);
i /= 2;
}
// System.out.println("插入成功");
}
private void swap(int[] nums, int index1, int index2) {
int temp = nums;
nums = nums;
nums = temp;
}
```
**移除堆顶元素**（自顶向下）思路：
- 将堆尾元素放至堆顶，依次和左子节点、右子节点比较，将最大值放至堆顶。
-交换位置后继续与子节点比较，直到左右子节点都小于当前节点。
```java
public void removeMax(int[] nums ,int length) {
if (length == 0)
return;
nums = nums; // 将末位值放到堆顶
length--;
heapfy(nums, length, 1);
}
public void heapfy(int[] nums, int length, int i) // 自顶向下堆化
{
// 判断当前堆顶是否都大于子节点，
// 否则把最大值与堆顶交换
int maxPos = i;
while (true) {
maxPos = i;
if (i * 2 <= length && nums < nums) {
maxPos = 2 * i;
}
if (2 * i + 1 <= length && nums < nums) {
maxPos = 2 * i + 1;
}
if (maxPos == i)
break; // 说明子节点都小于堆顶
swap(nums, i, maxPos);
i = maxPos;
}
}
```
# 堆的实际应用
>对一个点击量很大的新闻网站，在首页实时展示热度前 10 的新闻摘要，每隔 1 小时对前 10 进行一次数据更新
>通过堆和散列表来实现。
我的思路：
1. 首先，以每条新闻的摘要为键( key )，新闻的点击量为值( value )，生成对应的散列表。（若散列表过长可以取模分成小表）
2. 再根据点击量生成容量为 10
的小顶堆，新闻点击量更新时只需要和堆顶的新闻点击量比较，若大于堆顶，则更新堆数据（先移除堆顶元素，再插入新元素），否则无需对堆进行操作。
3. 前端每隔 1 小时向后端获取 1 次排名，后端根据堆中存放的前 10 点击量，在散列表中取出对应的新闻摘要返回前端页面，前端更新数据。
总结：这是堆应用中典型的 **求 Top K 问题**。实际上就是维护 1 个容量为 K 的小顶堆，根据数据来更新堆。
# 总结
堆学习的重点在于理解堆化的过程，在不同的场景中需要选择合适的堆化。（文章中出现错误，可以直接在评论中指出） 。。。。。。。。。。我以为是pwn里的堆入门，发觉是堆排序的的呀，虽然我也不会这个 谢谢LZ分享 冰露㊣神 发表于 2019-4-7 21:04
。。。。。。。。。。我以为是pwn里的堆入门，发觉是堆排序的的呀，虽然我也不会这个
你说的应该是计算机操作系统里表示的堆栈溢出吧 hack_hu 发表于 2019-4-8 11:00
你说的应该是计算机操作系统里表示的堆栈溢出吧
是的啊，堆好像入门
页:
[1]