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;
    }
}