Heap
A heap is an implementation of priority queue
堆可能的操作：
insert(s , x )
max(s)
extract-max(s): get and remove the max element in the set(s)
increase_key(s,x,k): increase the value of x's key to new value key.(k为x的优先值， 简写为k)
把堆看成一个棵树，有如下的特性：
- （1）含有n个元素的堆的高度是lgn。
- （2）当用数组表示存储了n个元素的堆时，叶子节点的下标是n/2+1，n/2+2，……，n。
- （3）在最大堆中，最大元素该子树的根上；在最小堆中，最小元素在该子树的根上。
image.png
Heap的存储
- 其实每一个数组都可以看作一个堆，通过max_heapify(A, index)可以将其转化为"大堆"。
- 对于一个数组：
- root of tree : first element(i = 1)
- parent(i) = i / 2
- left(i) = 2i
- right(i) = 2i+1
Max_Heapify(A,index)
- Max_Heapify(A,index)：堆化，可以说是堆的核心操作，你总是需要不停的调用它（递归）。
- A:存放堆的数组，index：需要调整的子树的根节点的索引
image.png
build_max_heap
- pseudocode:伪代码
Build_Max_Heap(A):
for i = n/2 downto 1
do max_heapify(A,i);
为什么是从i = n/2开始：
- 我们知道堆所对应的二叉树的叶子结点不需要参与max_heapify的调整。
当用数组表示存储了n个元素的堆时，叶子节点的下标是n/2+1，n/2+2，……，n。
HeapSort
- ①Build_max_heap from unordered array
- ②Find max element A[1]
- ③Swap elements A[n] with A[1]
now max element is at the end of array - ④Discard（去掉） node n from heap decrementing heap size
- ⑤new root may violate maxheap, but children are max_heap
返回第②，以此循环
C语言实现
https://github.com/yuanoOo/Algorithm/tree/master/HeapSort
#include<stdio.h>
#define PARENT(i) (i/2)
#define LEFT(i) (2*i)
#define RIGHT(i) (2*i + 1)
#define SHOULD 0x7fffffff
void max_heapify(int* a, int index, int length);
void max_heapify_loop(int *a, int index, int length);
void build_max_heap(int* a,int length);
void heapSort(int *a, int length);
void heapSort_loop(int *a, int length);
int main()
{
int a[] = {SHOULD,5,3,17,10,84,19,6,22,9,35};
build_max_heap(a, 10);
heapSort_loop(a, 10);
for(int i=1;i<11;++i)
printf("%d ",a[i]);
return 0;
}
//默认采用递归
void max_heapify(int* a, int index, int length)
{
int left,right,largest;//记录的均是数组下标
int temp;
left = LEFT(index);
right = RIGHT(index);
//find the largest value among left and right and i
if(left <= length && a[left] > a[index] )
largest = left;
else
largest = index;
if(right <= length && a[right] > a[largest])
largest = right;
//exchange index with largest
if(index != largest)
{
temp = a[index];
a[index] = a[largest];
a[largest] = temp;
//recursive call the function,adjust from largest
max_heapify(a,largest,length);
}
}
//利用循环max_heapify
void max_heapify_loop(int *a, int index, int length)
{
int left,right,largest,temp;
while(1)
{
left = LEFT(index);
right = RIGHT(index);
//find the largest value among left and right and i
if(left <= length && a[left] > a[index])
largest = left;
else
largest = index;
if(right <= length && a[right] > a[largest])
largest = right;
//exchange index with largest
if(index != largest)
{
temp = a[index];
a[index] = a[largest];
a[largest] = temp;
index = largest;
}else{
break;
}
}
}
//给出一个数组，将其转化为heap，自底向上
void build_max_heap(int* a,int length)
{
for(int i = length / 2; i > 0; i--)
max_heapify_loop(a,i,length);
}
//only accept the max_heap or min_heap
void heapSort(int *a, int length)
{
//recursive's exit
if(length == 1)
return;
int *maxNum = &a[1];
//swap a[1] with a[n]
int temp = *maxNum;
*maxNum = a[length];
a[length] = temp;
//discard node n from heap decrementing heap size
--length;
max_heapify_loop(a,1,length);//new root may violate max_heap, So heapify
//recursive
heapSort(a,length);
}
//循环实现，only accept the max_heap or min_heap
void heapSort_loop(int *a, int length)
{
while(1)
{
int *maxNum = &a[1];
//swap maxNum with a[n]
int temp = *maxNum;
*maxNum = a[length];
a[length] = temp;
//discard node n from heap decrementing heap size
--length;
max_heapify_loop(a,1,length);//new root may violate max_heap, So heapify
if(length == 1)
break;
}
}
