数组实现堆

完全二叉树

完全二叉树，逐层而下，从左到右，结点的位置完全由其序号觉得，因此可以用数组来实现。

计算各结点下标的公式，其中$r$ 表示结点的下标，范围在0 ~ n-1 之间，n是二叉树结点的总数。

$Parent(r)= \lfloor (r-1)/2 \rfloor$ 向下取整，当$r≠0$时

$Leftchild(r)=2r+1$,当$2r+1<n$时

$Rightchild(r)=2r+2$,当 $2r+2<n$ 时

$Leftsibling()=r-1$,当r为偶数时

$Rightsibling()=r+1$ ,当r为奇数并且$r+1<n$时

C++实现

完全二叉树的一个重要应用是最大堆和最小堆，最小堆就是儿子的值一定不小于父亲的值，树的节点从上到下，从左到右紧凑排列。这里给出最小堆的实现：

插入数值：在堆的末尾插入，然后不断向上提升，直到没有大小颠倒。

删除数值：首先把堆的最后一个节点的数值放到根上去，并且删除最后一个节点，然后不断向下交换直到没有大小颠倒为止。向下交换的时候如果2个儿子都比自己小，那么选择数值较小的儿子进行交换。

复杂度：建堆需要$\Theta(n)$ 的时间，但删除插入都和树深度成正比，时间复杂度是$\Theta(nlogn)$。

// ------------------- min heap --------------------------
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int MAX_N = 100;
int heap[MAX_N],sz=0; //sz is global variable, meaning the lengh of heap

void heap_push(int x){
    //own node's num.
    int node_index = sz++;
    while (node_index > 0) {
        int p = (node_index-1)/2; //i's parent
        if (heap[p] <= x) {
            break; // sequence is ok
        }
        // parent's value put down, node value go up
        heap[node_index] = heap[p];
        node_index = p;
    }
    heap[node_index] = x;
}

int heap_pop(){
    // min (root)
    int rec = heap[0];
    // the new temp root value, get it for compare and move it
    int x = heap[--sz];
    //replace from the root
    int i = 0;
    while (i*2+1 < sz) {
        //compare the children value
        int a = i*2+1;
        int b = i*2+2;
        if (b < sz && heap[b] < heap[a]) {
            a = b;
        }
        // sequence is right
        if (heap[a] >= x) {
            break;
        }
        // child's value go up
        heap[i] = heap[a];
        i=a;
    }
    heap[i] = x;
    return rec;
}

int main(){
    //push(3);
    heap_push(9);
    heap_push(2);
    heap_push(6);
    for (int i=0; i<sz; i++) {
        cout<<heap[i]<<endl;
    }
    cout<<"pop:"<<heap_pop()<<endl;
    cout<<"pop:"<<heap_pop()<<endl;
    
    // ------ standard package is the max queue ------
    priority_queue<int> qqueue;
    qqueue.push(-9);
    qqueue.push(-2);
    qqueue.push(-6);
    //loop until it is empty
    while (!qqueue.empty()) {
        cout<<-1 * qqueue.top()<<endl;
        qqueue.pop();
    }
    return 0;
}

Reference

1，《数据结构与算法分析》 Clifford A. Shaffer 等

2，《挑战程序设计》