EKsumic's Blog

let today = new Beginning();

Click the left button to use the catalog.

OR

关于Heap(堆)以及其相关算法(sink, swim以及heapify)

注意点

以下是二叉树(堆)相关:

  1. 堆不需要严格的左边大于右边。(指节点)
  2. 堆可以从小到大,也可以从大到小。(指节点value排序)
  3. 堆的节点值一定大于或一定小于子节点,但没左节点一定大于右节点这种规定,只有作为父节点值一定要大于子节点值这种。(注意这里都是谈的value而非下标,而且所叙述的大于子节点是大于两个子节点
  4. 堆不需要search算法,因为没有意义,最大值或最小值一定在顶部。(那么堆排序算法其实就是取顶值
  5. 堆的应用并没有那么广泛,所以sink和swim不算普遍意义上的叫法。(这个请注意一下,因为这边用的是日版教材)
  6. 另外堆,插入一个值并没有像之前二叉树那样,指针,找个位置插进去就可以了。(总之就是操作很复杂)
  7. 堆的话,一般先把要插入的值放在最末尾,这样一是能保证它还是个完全二叉树,而是方便我们交换值。(放在最末尾一般是开始swim操作,反过来则是sink)
  8. 插入→swim (insert触发了swim操作)
  9. 删除→sink (delete触发了sink操作)
  10. 删除一定是删除root节点,然后把最末尾的值给扔到root上。(因为除了root节点,你其他的都不好删,而且拿走root是和排序有点关系的)
  11. 然后,做sink操作的时候,一定是和最大的进行交换。
  12. 它的子节点必然是2i+1和2i+2。(小顶)
  13. 反过来是(i-1)/2和(i-2)/2。(大顶)
  14. root是最小值或者最大值。
  15. 必须是完全二叉树。
  16. heap保存形式是数组。
  17. 堆算法的时间复杂度为\(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;
}

 

This article was last edited at 2021-11-24 17:40:15

* *