Copyright notice: This article is an original article and follows
CC 4.0 BY-NC-ND
Copyright agreement. If you want to repost this article, please attach the original source link and this statement.
Source link:
https://www.v2know.com/MainPage/PreView/867
注意点
以下是二叉树（堆）相关：
- 堆不需要严格的左边大于右边。（指节点）
- 堆可以从小到大，也可以从大到小。（指节点value排序）
- 堆的节点值一定大于或一定小于子节点，但没左节点一定大于右节点这种规定，只有作为父节点值一定要大于子节点值这种。（注意这里都是谈的value而非下标，而且所叙述的大于子节点是大于两个子节点）
- 堆不需要search算法，因为没有意义，最大值或最小值一定在顶部。（那么堆排序算法其实就是取顶值）
- 堆的应用并没有那么广泛，所以sink和swim不算普遍意义上的叫法。（这个请注意一下，因为这边用的是日版教材）
- 另外堆，插入一个值并没有像之前二叉树那样，指针，找个位置插进去就可以了。（总之就是操作很复杂）
- 堆的话，一般先把要插入的值放在最末尾，这样一是能保证它还是个完全二叉树，而是方便我们交换值。（放在最末尾一般是开始swim操作，反过来则是sink）
- 插入→swim （insert触发了swim操作）
- 删除→sink （delete触发了sink操作）
- 删除一定是删除root节点，然后把最末尾的值给扔到root上。（因为除了root节点，你其他的都不好删，而且拿走root是和排序有点关系的）
- 然后，做sink操作的时候，一定是和最大的进行交换。
- 它的子节点必然是2i+1和2i+2。（小顶）
- 反过来是(i-1)/2和(i-2)/2。（大顶）
- root是最小值或者最大值。
- 必须是完全二叉树。
- heap保存形式是数组。
- 堆算法的时间复杂度为\(O(nlog{n})\)。
sink
#include "stdafx.h"
#include "stdlib.h"
//堆的二叉树只有父节点大于子节点这一条（或者反过来），不需要左边大于右边
//--heap堆的二叉树这里举的例子脚标默认是从小到大
//--子节点是父节点的2倍+1以及2倍+2
//注意，堆的表现形式是一维数组
//删除 --i是已经放好的位置 --n是数组的大小，用来检查是否越界 -- 针对大顶堆
void sink(int nums[],int n, int i)
{
//删除触发sink操作，删除一定是删除root节点
//去除最顶部root的节点，同时把最末尾的节点给按到root上了
//此时，堆属性被破坏
//这个时候，我们要执行sink操作（sift-down)，让顶部这个节点往下沉
//从堆的数组角度理解
int largest=i;
int l=2*i+1;
int r=2*i+2;
//如上所示，l,r,i，都是指index下脚标
if(l<n&&nums[l]>nums[largest])
largest=l;
if(r<n&&nums[r]>nums[largest])
largest=r;
if(largest!=i)
{
//对应序号的值交换
swap(&nums[i],&nums[largest]);
sink(nums,n,largest);
}
}
swim
//插入 -- 针对大顶堆 --n是数组大小，防止越界
void swim(int nums[],int n,int i)//i是已经放好的位置（这里的代码是没有放入操作的）
{
//插入到第一个，那说明不需要排，直接返回
if(i==0)
return;
int parent=(i-1)/2;
if(nums[parent]<nums[i])
{//parent的value比i小的话，交换
swap(&nums[i],&nums[parent]);//使得大值上浮
swim(nums,n,parent);
}
}
heapify
//存数组，n是size
void heapify(int nums[],int n)
{
int i;
for(i=(n-1-1)/2;i>=0;i--)//这个操作实际上是从最末尾找往上追溯父节点，做下沉操作
sink(nums,n,i);
}
补充
void swap(int *x,int *y)
{
int temp;
temp=*x;
*x=*y;
*y=temp;
}