什么是二叉堆
二叉堆是一种特殊的堆，它的父节点的值总是大于等于（或小于等于它的子节点值，称作小顶堆），这种堆叫做大顶堆。由于它具有完全二叉树的性质，所以可以使用数组来存储。当父节点的下标为ｉ，其左孩子的下标为2i，右孩子的下标为2i+1。
二叉堆在查找元素的时候，和普通的数组一样，时间复杂度为o(n)，但是在获取最大（最小）元素的时候，时间复杂度是o(1)。二叉堆每次插入和删除元素的时候，都需要对二叉堆进行一次调整，其时间复杂度为o(log(2n))。
二叉堆的插入与删除（最大堆举例）
- 二叉堆的插入步骤
- 首先把需要插入的元素放到二叉树的最末端（也就是数组中所有元素的最后）
- 从最末端去向上调整，具体来说就是不断将该节点和其父节点比较，如果父节点的值比插入节点的值小（对最小堆来说，父节点值比插入节点值大），就将父节点移动到当前位置，然后继续向上比较。否则到第３步。
３．如果当前父节点值比插入节点值大（对最小堆来说，插入点值比插入节点值小），就说明当前位置适合放入该插入的节点。那么将当前节点的值替换为插入节点的值，即完成插入操作。
- 二叉堆的删除步骤
- 首先查找到需要删除的元素的在数组中对应的下标。
２．将该下标对应的元素换成二叉树最末端的元素（即数组中最后一个元素）。
３．从当前下标的位置向下去调整，具体来说，首先计算出当前下标的左孩子的下标，如果当前节点有右孩子，那么比较左孩子和右孩子谁更大。将插入节点的值与左孩子和右孩子中最大的元素相比较，如果插入节点的值更小（对最小堆来说，插入节点值比当前孩子节点值大），那么将孩子节点的值放至其父亲节点，更新当前下标为替换的孩子节点下标，然后继续向下调整。否则到第４步。
４．将插入节点与左孩子和右孩子中最大的元素相比较，如果插入节点的值更大（对最小堆来说，插入节点值比当前节点值大），说明插入节点应该放到当前位置。放入之后，即完成删除操作。
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;
}
