二叉堆的理解与实现

什么是二叉堆

二叉堆是一种特殊的堆，它的父节点的值总是大于等于（或小于等于它的子节点值，称作小顶堆），这种堆叫做大顶堆。由于它具有完全二叉树的性质，所以可以使用数组来存储。当父节点的下标为ｉ，其左孩子的下标为2i，右孩子的下标为2i+1。
二叉堆在查找元素的时候，和普通的数组一样，时间复杂度为o(n)，但是在获取最大（最小）元素的时候，时间复杂度是o(1)。二叉堆每次插入和删除元素的时候，都需要对二叉堆进行一次调整，其时间复杂度为o(log(2n))。

二叉堆的插入与删除（最大堆举例）

• 二叉堆的插入步骤

1. 首先把需要插入的元素放到二叉树的最末端（也就是数组中所有元素的最后）
2. 从最末端去向上调整，具体来说就是不断将该节点和其父节点比较，如果父节点的值比插入节点的值小（对最小堆来说，父节点值比插入节点值大），就将父节点移动到当前位置，然后继续向上比较。否则到第３步。
   ３．如果当前父节点值比插入节点值大（对最小堆来说，插入点值比插入节点值小），就说明当前位置适合放入该插入的节点。那么将当前节点的值替换为插入节点的值，即完成插入操作。

• 二叉堆的删除步骤

1. 首先查找到需要删除的元素的在数组中对应的下标。
   ２．将该下标对应的元素换成二叉树最末端的元素（即数组中最后一个元素）。
   ３．从当前下标的位置向下去调整，具体来说，首先计算出当前下标的左孩子的下标，如果当前节点有右孩子，那么比较左孩子和右孩子谁更大。将插入节点的值与左孩子和右孩子中最大的元素相比较，如果插入节点的值更小（对最小堆来说，插入节点值比当前孩子节点值大），那么将孩子节点的值放至其父亲节点，更新当前下标为替换的孩子节点下标，然后继续向下调整。否则到第４步。
   ４．将插入节点与左孩子和右孩子中最大的元素相比较，如果插入节点的值更大（对最小堆来说，插入节点值比当前节点值大），说明插入节点应该放到当前位置。放入之后，即完成删除操作。

c++实现二叉堆的插入与删除

#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){
      // 先放末端，再向上调整
        nums.push_back(x);
        ++size;
        // 向上调整
        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){
          //　找到当前节点中左右孩子最大的元素下标
            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){
        //先用最后一个元素替换删除位置的元素，再向下调整
        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;
}