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