二叉堆

    二叉堆是一种用类似二叉树的形式构建的具有堆的性质的数据结构。

堆的性质： （以最大堆为例）

1. 堆顶元素为最大元素
2. 每个节点的元素值都大于其子女节点的元素值
3. 用数组实现堆，建堆的时间复杂度为 O(n)
4. 用堆进行排序，时间复杂度为 O(n*lgn)

二叉堆实现：(c++)

#define MAX_HEAP_SIZE 100
void Swap(int* a, int* b){
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
class Heap{
public:
    Heap(int n = 10) :
        heap_size_(n){
    }

    ~Heap(){
    }
    int LeftChild(int n){  //返回左子节点
        return 2 * n + 1;
    }
    int RightChild(int n){  //右子节点
        return 2 * n + 2;
    }
    int Parent(int n){    //父节点
        return (n - 1) / 2;
    }
    void AdjustElement(int pos, int value){  //将堆中的一个元素设置新值之后，调整该新值的位置
        heap_array_[pos] = value;
        AdjustElementUp(pos);
        AdjustElementDown(pos);
    }
    void AdjustElementDown(int pos){        //向下调整
        int left_child_pos = LeftChild(pos);
        int right_child_pos = RightChild(pos);
        int chg_pos = pos;
        if (left_child_pos < heap_size_ && heap_array_[left_child_pos] > heap_array_[chg_pos]){
            chg_pos = left_child_pos;
        }
        if (right_child_pos < heap_size_ && heap_array_[right_child_pos] > heap_array_[chg_pos]){
            chg_pos = right_child_pos;
        }

        if (chg_pos == pos){
            return;
        }
        else{
            Swap(heap_array_ + pos, heap_array_ + chg_pos);
            AdjustElementDown(chg_pos);
        }
    }
    void AdjustElementUp(int pos){        //向上调整
        while (pos > 0){
            int parent = Parent(pos);
            if (heap_array_[parent] < heap_array_[pos]){
                Swap(heap_array_ + pos, heap_array_ + parent);
            }
            pos = parent;
        }
    }

    void BuildHeap(int n, int *arr){    //从给定数组构建一个堆
        heap_size_ = n;
        for (int i = 0; i < n; i++){
            heap_array_[i] = arr[i];
        }
        for (int i = heap_size_ / 2 - 1; i >= 0; i--){
            AdjustElement(i, heap_array_[i]);
        }
    }
    int PopHeap(){                //弹出堆顶的元素
        if (heap_size_ <= 0){
            cout << "heap size <= 0, heap is empty!" << endl;
            return -1;
        }

        int top = heap_array_[0];
        int value = heap_array_[heap_size_ - 1];
        heap_size_--;
        AdjustElement(0, value);
        return top;
    }
    void HeapSort(int n, int*arr){        //堆排序
        BuildHeap(n, arr);
        for (int i = 0; i < n; i++){
            int ele = PopHeap();
            cout << "Element " << i << " : " << ele << endl;
        }
    }
private:
    int heap_array_[MAX_HEAP_SIZE];
    int heap_size_;
};