什么是二叉堆

二叉堆是一種特殊的堆，它的父節(jié)點(diǎn)的值總是大于等于（或小于等于它的子節(jié)點(diǎn)值，稱作小頂堆），這種堆叫做大頂堆。由于它具有完全二叉樹的性質(zhì)，所以可以使用數(shù)組來存儲(chǔ)。當(dāng)父節(jié)點(diǎn)的下標(biāo)為ｉ，其左孩子的下標(biāo)為2i，右孩子的下標(biāo)為2i+1。
二叉堆在查找元素的時(shí)候，和普通的數(shù)組一樣，時(shí)間復(fù)雜度為o(n)，但是在獲取最大（最?。┰氐臅r(shí)候，時(shí)間復(fù)雜度是o(1)。二叉堆每次插入和刪除元素的時(shí)候，都需要對(duì)二叉堆進(jìn)行一次調(diào)整，其時(shí)間復(fù)雜度為o(log(2n))。

二叉堆的插入與刪除（最大堆舉例）

• 二叉堆的插入步驟

1. 首先把需要插入的元素放到二叉樹的最末端（也就是數(shù)組中所有元素的最后）
2. 從最末端去向上調(diào)整，具體來說就是不斷將該節(jié)點(diǎn)和其父節(jié)點(diǎn)比較，如果父節(jié)點(diǎn)的值比插入節(jié)點(diǎn)的值小（對(duì)最小堆來說，父節(jié)點(diǎn)值比插入節(jié)點(diǎn)值大），就將父節(jié)點(diǎn)移動(dòng)到當(dāng)前位置，然后繼續(xù)向上比較。否則到第３步。
   ３．如果當(dāng)前父節(jié)點(diǎn)值比插入節(jié)點(diǎn)值大（對(duì)最小堆來說，插入點(diǎn)值比插入節(jié)點(diǎn)值?。驼f明當(dāng)前位置適合放入該插入的節(jié)點(diǎn)。那么將當(dāng)前節(jié)點(diǎn)的值替換為插入節(jié)點(diǎn)的值，即完成插入操作。

• 二叉堆的刪除步驟

1. 首先查找到需要?jiǎng)h除的元素的在數(shù)組中對(duì)應(yīng)的下標(biāo)。
   ２．將該下標(biāo)對(duì)應(yīng)的元素?fù)Q成二叉樹最末端的元素（即數(shù)組中最后一個(gè)元素）。
   ３．從當(dāng)前下標(biāo)的位置向下去調(diào)整，具體來說，首先計(jì)算出當(dāng)前下標(biāo)的左孩子的下標(biāo)，如果當(dāng)前節(jié)點(diǎn)有右孩子，那么比較左孩子和右孩子誰更大。將插入節(jié)點(diǎn)的值與左孩子和右孩子中最大的元素相比較，如果插入節(jié)點(diǎn)的值更?。▽?duì)最小堆來說，插入節(jié)點(diǎn)值比當(dāng)前孩子節(jié)點(diǎn)值大），那么將孩子節(jié)點(diǎn)的值放至其父親節(jié)點(diǎn)，更新當(dāng)前下標(biāo)為替換的孩子節(jié)點(diǎn)下標(biāo)，然后繼續(xù)向下調(diào)整。否則到第４步。
   ４．將插入節(jié)點(diǎn)與左孩子和右孩子中最大的元素相比較，如果插入節(jié)點(diǎn)的值更大（對(duì)最小堆來說，插入節(jié)點(diǎn)值比當(dāng)前節(jié)點(diǎn)值大），說明插入節(jié)點(diǎn)應(yīng)該放到當(dāng)前位置。放入之后，即完成刪除操作。

c++實(shí)現(xiàn)二叉堆的插入與刪除

#include <iostream>
#include <vector>
using namespace std;

class Max_Heap{
private:
    vector<int> nums;
    int size;
public:
    Max_Heap(): size(0){}
    ~Max_Heap() {
        nums.clear();
        size = 0;
    };

    int get_size() const{
        return size;
    }

    void maxheap_filterup(int index){
        int curr_index = index;
        int data = nums[curr_index];
        int parent_index = (curr_index - 1) / 2;

        while(curr_index > 0){
            if(nums[parent_index] >= data)
                break;
            else{
                nums[curr_index] = nums[parent_index];
                curr_index = parent_index;
                parent_index = (curr_index - 1) / 2;
            }
        }
        nums[curr_index] = data;
    }

    void insert(int x){
      // 先放末端，再向上調(diào)整
        nums.push_back(x);
        ++size;
        // 向上調(diào)整
        maxheap_filterup(size-1);
    }

    int get_data_index(int data)const{
        int j = 0;
        for (j ; j < size ; ++j) {
            if(nums[j] == data)
                break;
        }

        return j;
    }


    void maxheap_filterdown(int start, int end){
        int curr_index = start;
        int child_index_l = 2*curr_index + 1;
        int data = nums[curr_index];

        while(child_index_l <= end){
          //　找到當(dāng)前節(jié)點(diǎn)中左右孩子最大的元素下標(biāo)
            if(child_index_l < end && nums[child_index_l+1] >= nums[child_index_l])
                ++child_index_l;
            if(data >= nums[child_index_l])
                break;
            else{
                nums[curr_index] = nums[child_index_l];
                curr_index = child_index_l;
                child_index_l = child_index_l*2 + 1;
            }
        }
        nums[curr_index] = data;
    }

    void remove(int x){
        //先用最后一個(gè)元素替換刪除位置的元素，再向下調(diào)整
        int index = get_data_index(x);
        nums[index] = nums[size - 1];
        --size;
        maxheap_filterdown(index, size-1);
    }

    void show()const{
        cout<<"current max heap is:\n";
        for (int i = 0; i < size ; ++i) {
            cout<<nums[i]<<" ";
        }
        cout<<endl;
    }

};
int main() {

    Max_Heap max_heap;
    vector<int> n = {80, 90, 10, 40, 50, 20, 30, 70, 60,85};
    //vector<int> n = {90,85,70,60,80,30,20,10,50,40};
    for (int i = 0; i < n.size(); ++i) {
        max_heap.insert(n[i]);
    }
    max_heap.show();
    max_heap.remove(60);
    max_heap.show();
    return 0;
}