- 堆的基本概念和性质
- 基本概念
- 性质
- 堆排序的思想和基本步骤
- 堆排序基本步骤
- 如何由一个无序序列建堆
- 方法一：向堆中添加元素实现建堆
- 方法二：自下而上的调整堆来达到建堆
- 如何在交换堆顶元素后调整当前无序区成为一个新堆
- 堆排序的复杂度
- 更改堆元素后重建堆时间复杂度：O(nlogn)
- 通过自下而上调整堆初始化建堆过程时间复杂度：O(n)
- 通过向堆添加元素初始化建堆过程的时间复杂度：O(nlogn)
- 空间复杂度为常数：O(1)
- TopK问题
- 中位数问题
- 堆：堆是一个近似完全二叉树的结构，采用数列存储。
- 大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
- 小顶堆：每个节点的值都小于或者等于它的左右子节点的值。
- 用数组arr存储堆结构的时候（下标从0开始），对于下标为 i 的节点，他的左子节点的下标为 2 × i + 1,右子节点的下标为 2 × i + 2，父节点为 (i-1)/2
- 大顶堆：（注意 i 可以取到 arr.length/2-1 ,因为最后一个非叶子节点存在右子节点时，arr.length一定是奇数，根据c语言整数除法的向下取整规则，此时右子节点的下标为 arr.length-1,不会越界。 ）
a r r [ i ] ≥ a r r [ 2 × i + 1 ] a n d a r r [ i ] ≥ a r r [ 2 × i + 2 ] , 0 ≤ i ≤ a r r . l e n g t h / 2 − 1 arr[i] geq arr[2times i+1] and arr[i] geq arr[2 times i +2] , 0 leq i leq arr.length/2-1 arr[i]≥arr[2×i+1] and arr[i]≥arr[2×i+2], 0≤i≤arr.length/2−1 - 小顶堆：
a r r [ i ] ≤ a r r [ 2 × i + 1 ] a n d a r r [ i ] ≤ a r r [ 2 × i + 2 ] , 0 ≤ i ≤ a r r . l e n g t h / 2 − 1 arr[i] leq arr[2times i+1] and arr[i] leq arr[2 times i +2] , 0 leq i leq arr.length/2-1 arr[i]≤arr[2×i+1] and arr[i]≤arr[2×i+2], 0≤i≤arr.length/2−1 - 最后一个非叶子节点的下标为 arr.length/2 -1（arr.length>1）
证明 ：假设堆所对应的完全二叉树一共有n 层，第n 层的结点数目设为 x，并考虑c语言整数除法的向下取整规则。
根据等比数列求和公式可得， 结点总数 arr.length = 2n-1-1 + x ，则 arr.length/2 = 2n-2 + (x-1)/2
易知，叶子节点总数 = 2n-2+ x/2 (第 n-1层 节点总数为 2 n-2),
所以
非叶子节点总数 = { 2 n − 2 + x 2 , x 为奇数，即 a r r . l e n g t h 为偶数时 2 n − 2 + x 2 − 1 , x 为偶数，即 a r r . l e n g t h 为奇数时 非叶子节点总数=left{ begin{aligned} 2^{n-2}+frac{x}{2} &, & x为奇数，即arr.length为偶数时 \ 2^{n-2}+frac{x}{2} -1 &, & x为偶数，即arr.length为奇数时 end{aligned} right. 非叶子节点总数=⎩ ⎨ ⎧2n−2+2x2n−2+2x−1,,x为奇数，即arr.length为偶数时x为偶数，即arr.length为奇数时
根据c语言整数除法的向下取整规则，
x − 1 2 = { x 2 , x 为奇数，即 a r r . l e n g t h 为偶数时 x 2 − 1 , x 为偶数，即 a r r . l e n g t h 为奇数时 frac{x-1}{2}=left{ begin{aligned} frac{x}{2} &, & x为奇数，即arr.length为偶数时 \ frac{x}{2} -1 &, & x为偶数，即arr.length为奇数时 end{aligned} right. 2x−1=⎩ ⎨ ⎧2x2x−1,,x为奇数，即arr.length为偶数时x为偶数，即arr.length为奇数时
因此，非叶子节点总数 = arr.length/2，
又因为 下标从0开始，因此最后一个非叶子节点的下标为 arr.length/2 -1。
- 将初始待排序序列arr[0…n] ,n = arr.length-1构建成大顶堆(小顶堆)，此堆为初始的无序区;
- 将堆顶元素arr[0]与最后一个元素arr[n]交换，此时得到新的无序区arr[0…n-1]和新的有序区arr[n]
- 由于交换后新的堆顶arr[0]可能违反堆的性质，因此需要对当前无序区arr[0…n-1]调整为新堆，然后再次将arr[0]与无序区最后一个元素交换，得到新的无序区arr[0…n-2]和新的有序区arr[n-1,n]。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
- 因为已知，当 i>=1时，下标为 i 的节点的父节点的下标为 (i-1)/2
- 堆由一维数组存储
- 以构建大顶堆为例，当堆的元素数大于1时，对于新来的元素添加到数组的末尾，然后获取新元素的父节点在数组中的位置，比较新元素和父节点的值，如果父节点的值小于新元素的值，那么两者交换。以此类推，不断向上比较，直到根节点结束。
- 这里我对交换实现了部分优化，具体可看代码
void addHeap(vector方法二：自下而上的调整堆来达到建堆& arr, int a) { arr.push_back(a); int len = arr.size(); if (len == 1)return; int index = len - 1; for (int i = (index - 1) / 2; i >= 0; i = (i - 1) / 2) {// i 初值指向父节点 if (arr[i] >= a)//已经找到插入位置 break; if (arr[i] < a) {//数据下移，继续寻找插入位置 arr[index] = arr[i]; index = i; } if (i == 0)break;//因为(0-1)/2等于0,但是arr[0]有可能会和a进行比较，因此在此处跳出循环 } arr[index] = a; }
在了解自下而上的调整堆来达到建堆建堆之前，我们先了解如何在交换堆顶元素后调整当前无序区成为一个新堆。因为只要知道了如何在交换堆顶元素后调整当前无序区成为一个新堆，就可以从最后一个非叶子节点开始（对于所有的非叶子节点 ）自下而上的调整堆来达到建堆的目的。（因为对于当前的非叶子节点来说，经过自下而上的调整堆的过程，他的左右子树都是堆，符合调整堆的条件）
void HeapSort(vector如何在交换堆顶元素后调整当前无序区成为一个新堆& arr) { int len = arr.size(); if (len < 2)return; //把arr[0...len-1]建成大顶堆,采用自下而上的方式 for (int i = len / 2 - 1; i >= 0; --i) //从第一个非叶子节点开始 HeapAdjust(arr, i, len - 1); //不断的缩小无序区 for (int i = len - 1; i >= 1; --i) { //将堆顶记录和当前未经排序子序列arr[0...i]中最后一个记录相互交换 swap(arr[0], arr[i]); //将arr[0..i-1]重新调整为大堆顶 HeapAdjust(arr, 0, i - 1); } }
由于我们是将堆中最后一个元素和堆顶交换得到的当前无序区，因此根结点的左右子树均为堆，则仅需从根节点出发自上而下进行调整即可。
以调整大顶堆为例：
- 左/右子节点之间先进行相互比较，找到较大者。
- 再作父节点和子结点较大者之间的比较，若“>=”成立，则说明已找到插入位置 ，不需要继续往下调整。
- 否则，交换父节点与子节点较大者，从步骤一开始重复，直到找到插入位置。
注意：我的对交换实现了部分优化交换可以看代码部分。
void HeapAdjust(vector堆排序的复杂度 更改堆元素后重建堆时间复杂度：O(nlogn)& arr, int s, int m) { int temp = arr[s];// 暂存 arr[s],也就是当前的根节点 //自上而下的筛选过程; for (int i = 2 * s + 1; i <= m; i = 2 * i + 1) { // i 初值指向左孩子 // 左/右“子树根”之间先进行相互比较 if (i < m && arr[i] < arr[i + 1]) i++; // 令 i 指示较大数据节点的位置 //再作“根”和“子树根”之间的比较,若“>=”成立，则说明已找到插入位置 s ，不需要继续往下调整 if (temp >= arr[i])//特别注意这里是 break; // 否则数据上移，尚需继续往下调整 arr[s] = arr[i]; s = i; } arr[s] = temp; }
- 假设堆对应的完全二叉树的深度为k，则更改堆顶元素后，需要比较的次数至多为 2(k-1)，（系数为2是因为一次比较左右子节点，一次比较父节点和子节点）
- 对于包含n个数据的堆，对应的完全二叉树的深度 k = ⌊ l o g 2 n ⌋ + 1 k= lfloor log_{2}n rfloor +1 k=⌊log2n⌋+1
- 则调整 “堆顶” n -1次，总共进行的数据比较的次数不超过 2 ( ⌊ l o g 2 ( n − 1 ) ⌋ + ⌊ l o g 2 ( n − 2 ) ⌋ + . . . + ⌊ l o g 2 2 ⌋ ) < 2 n ( ⌊ l o g 2 n ⌋ ) 2(lfloor log_{2}(n-1) rfloor+lfloor log_{2}(n-2) rfloor+...+lfloor log_{2}2 rfloor)< 2n(lfloor log_{2}n rfloor) 2(⌊log2(n−1)⌋+⌊log2(n−2)⌋+...+⌊log22⌋)<2n(⌊log2n⌋)
- 因此，更改堆元素后重建堆时间复杂度为O(nlogn)
- 假设堆对应的完全二叉树的深度为k,则更改堆顶元素后，需要比较的次数至多为 2(k-1)
- 完全二叉树第 i 层的节点数目为：2i-1
- 则调整第 i 层的所有非叶子节点需要的比较次数总数至多 2i-1 × 2 ×（k - i ） 1<= i < k
- 所以初始化建堆过程的比较次数总数最多为 ∑ i = 1 k − 1 ( 2 i × ( k − i ) ) sum _{i=1}^{k-1} left( 2^{i} times (k-i) right) i=1∑k−1(2i×(k−i))
- 通过错位相减可以算出上式结果为 2k+1-2(k+1),将 k 和 n 的关系式带入可得 2 l o g 2 ⌊ n ⌋ + 2 − 2 ( l o g 2 ⌊ n ⌋ + 2 ) 2^{log_{2} lfloor n rfloor +2}-2(log_{2} lfloor n rfloor +2) 2log2⌊n⌋+2−2(log2⌊n⌋+2)
- 因此时间复杂度：O(n)
- 假设堆对应的完全二叉树的深度为k，则向堆中添加一个元素需要的比较次数至多为 k-1次
- 向第 i 层添加元素并调整堆至该层满节点需要的比较次数最多为 2i-1 ×（i- 1） 1<= i < k
- 构建包含n个元素的堆需要的比较次数最多为 ∑ i = 1 k ( 2 i − 1 × ( i − 1 ) ) sum _{i=1}^{k} left( 2^{i-1} times (i-1) right) i=1∑k(2i−1×(i−1))
- 通过错位相减可得上式的结果为 (k-1)2k+1+2,将 k 和 n 的关系式带入可得 l o g 2 ⌊ n ⌋ 2 l o g 2 ⌊ n ⌋ + 2 + 2 log_{2} lfloor n rfloor 2^{log_{2} lfloor n rfloor +2}+2 log2⌊n⌋2log2⌊n⌋+2+2
- 因此时间复杂度为：O(nlogn)
堆排序是就地排序，空间复杂度为常数：O(1)
TopK问题如果在海量数据中找出最大的K个数字，可以选择维护一个大小为K的小顶堆
- 首先等待前k个数据利用自下而上的方法构造小顶堆，需要的比较次数最多为 2 l o g 2 ⌊ k ⌋ + 2 − 2 ( l o g k ⌊ k ⌋ + 2 ) 2^{log_{2} lfloor k rfloor +2}-2(log_{k} lfloor k rfloor +2) 2log2⌊k⌋+2−2(logk⌊k⌋+2)
- 或者对于流入的前 k 个数据直接利用添加元素的方式构造堆，需要的比较次数最多为 l o g 2 ⌊ k ⌋ 2 l o g 2 ⌊ k ⌋ + 2 + 2 log_{2} lfloor k rfloor 2^{log_{2} lfloor k rfloor +2}+2 log2⌊k⌋2log2⌊k⌋+2+2
- 对于接下来流入的数据，如果小于堆顶就舍弃；如果大于堆顶，就置换堆顶，然后自上而下调整堆。
- 这样一来，小顶堆中维护的永远是最大的 K 个元素。
- 对于接下来的 n-k 个数据最多需要的比较次数： ( n − k ) × 2 ⌊ l o g 2 k ⌋ (n-k)times 2lfloor log_{2}k rfloor (n−k)×2⌊log2k⌋
- 因此，对于n个数据的TopK问题，最多比较的次数等于上面两部分次数之和，又因为n远远大于k，所以，时间复杂度等于O(n）
堆也可以用于求解中位数，数据量可能很大且源源不断到来。
注意：如果元素个数是偶数，那么我们假定中位数取任意一个都可以。
有了上面的例子，这里就很好理解了。我们使用两个堆，一个最大堆，一个最小堆，步骤如下：
- 添加的第一个元素作为中位数 m，最大堆维护 <= m 的元素，最小堆维护 >= m 的元素，两个堆都不包含 m。
- 当添加第二个元素 e 时，将 e 与 m 比较，若 e <= m，则将其加入到最大堆中，否则加入到最小堆中。
- 如果出现最小堆和最大堆的元素个数相差 >= 2，则将 m 加入元素个数少的堆中，然后让元素个数多的堆将根节点移除并赋值给 m。
- 以此类推不断更新。
