《恋上数据结构与算法一》笔记（十六）堆

目录

• 问题思考
• Top K问题
• 堆（Heap）
• 堆的基本接口设计
• 二叉堆(Binary Heap)
• 获取最大值
• 最大堆 - 添加
• 最大堆 - 添加 - 总结 - 上滤
• 最大堆 – 添加 – 交换位置的优化
• 最大堆 - 删除
• 最大堆 - 删除总结 - 下滤
• 最大堆 – 批量建堆(Heapify)
• 最大堆 – 批量建堆 – 效率对比
• Top K的问题

一 问题思考

设计一种数据结构，用来存放整数，要求提供 3 个接口

• 添加元素
• 获取最大值
• 删除最大值

0	1	2	3	4	5	6
31	66	17	15	28	20	59

0	1	2	3	4	5	6
15	17	20	28	31	59	66

各个数据结构对比

	获取最大值	删除最大值	添加元素
动态数组\双向链表	O(n)	O(n)	O(1)
有序动态数组\双向链表	O(1)	O(1)	O(n)	全排序有点浪费
BBST	O(logn)	O(logn)	O(logn)	杀鸡用了牛刀

有没有更优的数据结构？
堆

获取最大值：O(1)
删除最大值：O(logn)
添加元素：O(logn)

二 Top K问题

什么是 Top K 问题

• 从海量数据中找出前 K 个数据

比如：从 100 万个整数中找出最大的 100 个整数

Top K 问题的解法之一：可以用数据结构堆来解决

三 堆（Heap）

堆(Heap)也是一种树状的数据结构(不要跟内存模型中的堆空间混淆)，常见的堆实现有

• 二叉堆(Binary Heap，完全二叉堆)
• 多叉堆(D-heap、D-ary Heap)
• 索引堆(Index Heap)
• 二项堆(Binomial Heap)
• 斐波那契堆(Fibonacci Heap)
• 左倾堆(Leftist Heap，左式堆)
• 斜堆(Skew Heap)

堆的一个重要性质

• 任意节点的值总是≥( ≤ )子节点的值
• 如果任意节点的值总是≥ 子节点的值，称为:最大堆、大根堆、大顶堆
• 如果任意节点的值总是 ≤ 子节点的值，称为:最小堆、小根堆、小顶堆

◼ 由此可见，堆中的元素必须具备可比较性(跟二叉搜索树一样)

image.png image.png

四 堆的基本接口设计

// 元素的数量
- (int)size();
// 是否为空
- (bool)isEmpty();
// 清空
- (void)clear();
// 添加元素
- (void)add:(id)element;
// 获得堆顶元素
- (id)get();
 // 删除堆顶元素
- (id)remove();
// 删除堆顶元素的同时插入一个新元素
- (id)replace:(id)element;

五 二叉堆(Binary Heap)

二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆

鉴于完全二叉树的一些特性，二叉堆的底层(物理结构)一般用数组实现即可

索引 i 的规律( n 是元素数量)

• 如果 i = 0 ，它是根节点
• 如果 i > 0 ，它的父节点的索引为floor( (i – 1) / 2 )
• 如果 2i + 1 ≤ n – 1，它的左子节点的索引为 2i + 1
• 如果 2i + 1 > n – 1 ，它无左子节点
• 如果 2i + 2 ≤ n – 1 ，它的右子节点的索引为 2i + 2
• 如果 2i + 2 > n – 1 ，它无右子节点

image.png

0	1	2	3	4	5	6	7	8	9
72	68	50	43	38	47	21	14	40	3

六 获取最大值

- (id)get {
    [self emptyCheck];
    return self.elements[0];
}

#pragma mark - private

- (void)emptyCheck {
    if (self.size == 0) {
        // 中断执行
    }
}

七 最大堆 - 添加

image.png

八 最大堆 - 添加 - 总结 - 上滤

image.png

循环执行以下操作(图中的 80 简称为 node)

• 如果 node > 父节点
  • 与父节点交换位置
  • 如果 node ≤ 父节点，或者 node 没有父节点，退出循环

这个过程，叫做上滤(Sift Up)，时间复杂度:O(logn)

• 测试代码

/// 建立小顶堆
- (void)test2 {
    BinaryHeap *heap = [[BinaryHeap alloc] init];
    int nums[] = {88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37};
    
    int num = sizeof(nums) / sizeof(int);
    for (int i = 0; i < num; i++) {
        [heap add:@(nums[i])];
    }
    
    [heap  print];
}

• 运行结果如下

2020-03-14 10:04:24.015514+0800 16_Heap[59557:7687718] i = 0, element = 98
2020-03-14 10:04:24.015665+0800 16_Heap[59557:7687718] i = 1, element = 88
2020-03-14 10:04:24.015751+0800 16_Heap[59557:7687718] i = 2, element = 70
2020-03-14 10:04:24.015851+0800 16_Heap[59557:7687718] i = 3, element = 44
2020-03-14 10:04:24.015939+0800 16_Heap[59557:7687718] i = 4, element = 85
2020-03-14 10:04:24.016020+0800 16_Heap[59557:7687718] i = 5, element = 36
2020-03-14 10:04:24.016092+0800 16_Heap[59557:7687718] i = 6, element = 53
2020-03-14 10:04:24.016175+0800 16_Heap[59557:7687718] i = 7, element = 18
2020-03-14 10:04:24.016253+0800 16_Heap[59557:7687718] i = 8, element = 41
2020-03-14 10:04:24.016326+0800 16_Heap[59557:7687718] i = 9, element = 16
2020-03-14 10:04:24.016512+0800 16_Heap[59557:7687718] i = 10, element = 81
2020-03-14 10:04:24.016912+0800 16_Heap[59557:7687718] i = 11, element = 6
2020-03-14 10:04:24.017082+0800 16_Heap[59557:7687718] i = 12, element = 23
2020-03-14 10:04:24.017290+0800 16_Heap[59557:7687718] i = 13, element = 43
2020-03-14 10:04:24.017443+0800 16_Heap[59557:7687718] i = 14, element = 37

• 转换为图表显示

image.png

九 最大堆 – 添加 – 交换位置的优化

一般交换位置需要3行代码，可以进一步优化

将新添加节点备份，确定最终位置才摆放上去

image.png

仅从交换位置的代码角度看
可以由大概的 3 * O(logn)优化到1 * O(logn) + 1

十 最大堆 - 删除

image.png

十一 最大堆 - 删除总结 - 下滤

image.png

1. 用最后一个节点覆盖根节点
2. 删除最后一个节点
3. 循环执行以下操作（图中的43简称为node）
   3.1 如果 node < 最大的子节点，与最大的子节点交换位置
   3.2 如果 node ≥ 最大的子节点， 或者 node 没有子节点，退出循环

这个过程，叫做下滤(Sift Down)，时间复杂度：O(logn)

同样的，交换位置的操作可以像添加那样进行优化

十二 最大堆 – 批量建堆(Heapify)

批量建堆，有 2 种做法

• 自上而下的上滤
• 自下而上的下滤

image.png

12.1 最大堆 – 批量建堆 – 自上而下的上滤

image.png

for (int i = 0; i < size; i++) {
    siftUp(i);
}

12.2 最大堆 – 批量建堆 – 自下而上的下滤

image.png

for (int i = (size >> 1) - 1; i >= 0; i--) {
    siftDown(i);
}

十三最大堆 – 批量建堆 – 效率对比

image.png

13.1最大堆 – 批量建堆 – 效率对比

所有节点的深度之和

• 仅仅是叶子节点，就有近 n/2 个，而且每一个叶子节点的深度都是 O(logn) 级别的
• 因此，在叶子节点这一块，就达到了 O(nlogn) 级别
• O(nlogn) 的时间复杂度足以利用排序算法对所有节点进行全排序

所有节点的高度之和

• 假设是满树，节点总个数为 n，树高为 h，那么 n = 2h − 1
• 所有节点的树高之和H(n)=20 ∗ (h−0) +21 ∗ (h−1) +22 ∗ (h−2) +⋯+2h−1 ∗ h− h−1
• H(n)=h∗ 20+21+22+⋯+2h−1 − 1∗21+2∗22+3∗23+⋯+ h−1 ∗2h−1 * H(n)=h∗ 2h −1 − h−2 ∗2h+2
• H(n) = h∗2h −h−h∗2h +2h+1 −2
• H(n) = 2h+1 −h−2 = 2∗(2h −1)−h = 2n −h = 2n−log2(n+1) = O(n)

13.2 公式推导

S(h) = 1∗21 +2∗22 +3∗23 +⋯+ h−2 ∗2h−2 + h−1 ∗2h−1 
2S(h)=1∗22+2∗23+3∗24+⋯+ h−2 ∗2h−1+ h−1 ∗2h 
S(h)–2S(h)=[21+22+23+⋯+2h−1]− h−1 ∗2h=(2h−2)− h−1 ∗2h
S(h) = h−1 ∗2h −(2h −2) = h−2 ∗2h +2

13.3 疑惑

以下方法可以批量建堆么

• 自上而下的下滤
• 自下而上的上滤

上述方法不可行，为什么?
认真思考【自上而下的上滤】、【自下而上的下滤】的本质

十四 Top K的问题

从 n 个整数中，找出最大的前 k 个数( k 远远小于 n )

如果使用排序算法进行全排序，需要 O(nlogn) 的时间复杂度

如果使用二叉堆来解决，可以使用 O(nlogk) 的时间复杂度来解决

• 新建一个小顶堆
• 扫描 n 个整数
  • 先将遍历到的前 k 个数放入堆中
  • 从第 k + 1 个数开始，如果大于堆顶元素，就使用 replace 操作(删除堆顶元素，将第 k + 1 个数添加到堆中)
• 扫描完毕后，堆中剩下的就是最大的前 k 个数

如果是找出最小的前 k 个数呢?

• 用大顶堆

• 如果小于堆顶元素，就使用 replace 操作

• 测试代码如下

// 找出最大的前K个数
- (void)test3 {
    // 新建一个小顶堆
    BinaryHeap *heap = [[BinaryHeap alloc] init];
    heap.delegate = self;
    int nums[] = {51, 30, 39, 92, 74, 25, 16, 93,
        91, 19, 54, 47, 73, 62, 76, 63, 35, 18,
        90, 6, 65, 49, 3, 26, 61, 21, 48};
    int k = 3;
    
    // 找出最大的前K个数
    int num = sizeof(nums) / sizeof(int);
    for (int i = 0; i < num; i++) {
        if (heap.size < k) {    // 前k个数添加到小顶堆
            [heap add:@(nums[i])];
        } else if (nums[i] > [[heap get] intValue]) {   // 如果是第 k + 1 个数，并且大于堆顶元素
            [heap replace:@(nums[i])];
        }
    }
    [heap print];
}

#pragma mark - BinaryHeapDelegate

- (int)compare:(NSNumber *)num1 num2:(NSNumber *)num2 {
    return num2.intValue - num1.intValue;
}

• 运行结果如下

2020-03-14 10:38:51.341735+0800 16_Heap[60757:7724048] i = 0, element = 91
2020-03-14 10:38:51.341888+0800 16_Heap[60757:7724048] i = 1, element = 93
2020-03-14 10:38:51.341999+0800 16_Heap[60757:7724048] i = 2, element = 92

---

项目链接地址 - 16_Heap

---

本文参考 MJ老师的 恋上数据结构与算法

---

《恋上数据结构与算法一》笔记

---

本人技术水平有限，如有错误欢迎指正。
书写整理不易，您的打赏与点赞是对我最大的支持和鼓励。

---