堆和优先队列笔记

堆的基础知识

完全二叉树(complete binary tree)-堆、优先队列
1、编号为i的子节点：左孩子编号2i， 右孩子编号2i+1
2、可以用连续空间存储(数组)=》子节点和父节点编号有关系

我们使用一个数组来模拟，这表示的是一个实际方面的数据结构，但是我们在思维方面上可以看成一个完全二叉树。

堆：基于完全二叉树的一种结构

• 大顶堆：任意的三元组之间，如果父节点的值都大于子节点的值（根节点是最大值）
• 小顶堆：任意三元组之间，如果父节点的值都小于子节点的值（根节点是最小值）

     12               3
     /\              / \
    11 10           7    4
    /\ /\           /\   /\
   6 7 9 3         10 12 9 6 
   /\               /\
  4 5              15 14
     大顶堆          小顶堆

拓展

数据结构：结构定义(定义一种结构，定义它的性质) + 结构操作(维护这个性质)

• 数据结构：定义一种性质，并维护这种性质
• 堆：适合维护集合的最值

堆操作

• 堆–尾部插入调整–》向上调整
  1. 比父节点大的就和父节点交换 递归向上调整
  2. 这个过程称为SIFT-UP
• 堆–头部弹出调整–》向下调整
  1. 用最后一个元素(叶子节点)补位 递归向下调整
  2. 这个过程称为SIFT-DOWN
• 堆-》尾部插入，头部弹出->队列-》又不是普通队列(每次弹出都是最大值或最小值-》当成优先级的话，每次弹出的是优先级最高的元素)=》优先级队列

堆-优先队列

普通队列	优先队列
尾部入队	尾部可以插入
头部出队	头部可以弹出
先进先出	每次出队权值(最大/最小的元素)
数组实现	数组实现，逻辑上看成一个堆

堆是优先队列的一种实现方式

堆的基础应用

LeetCode 剑指Offer40. 最小的k个数
LeetCode 1046 最后一块石头的重量
LeetCode 703 数据流中的第K大元素
LeetCode 373 查找和最小的K对数字
LeetCode 215 数组中的第K个最大元素

堆的进阶应用

设计推特
前K个高频单词
连续中值
数据流的中位数
积压订单中的订单总数

智力发散题

丑数II
超级丑数
移除石子的最大得分