二叉堆

获取堆顶：就是获取数组第一个元素

元素删除：先获取数组最后一个元素，与要删除的元素交换，把最后一个元素下沉并且不能与要删除的元素交换，下沉后将要删的删掉

每个元素的左右子树和父类都有固定的公式，左子树位2 * id+1，右子树位2 * id+2，父节点位（id-1）/2。

上浮函数：如果当前访问节点为0也就是根节点的时候，则递归函数结束，若当前不为零，则找他的父节点，如果是当前节点比父节点更优则交换当前节点和父节点，继续上浮操作（只需要比较自己和父节点）

下沉函数：（除了比较自己和子节点，还要比较那个子节点更优，也就是三个节点互相比较，谁赢继承权在谁手上），如果我的左儿子在数组范围内并且比当前获得继承权，如果有儿子在数组范围内并且比当前继承权的人更优那么他获得，最后，如果继承权节点和不是我自己，那么我就移交它，和继承节点交换位置，继续下沉。

堆的元素插入：我们需要将要插入元素查到堆的尾部，再进行一个上浮操作。

删除操作：删除第0个元素，先将第0个元素和最后一个元素交换，然后将堆的大小-1，然后将当前堆顶进行一个下沉操作。（因为他肯定是比较小的，所以一定能回到原先的位置）。

获取堆顶：直接返回第0个元素。

#include<iostream>
#include<algorithm>
using namespace std;
​
class Heap {
public:
    int* heap;
    int heapSize;
    int capacity;
​
    Heap();
    
    Heap(int capacity);
    ~Heap();
    void insert(int value);
    int lson(int i);
    int rson(int i);
    int parent(int i);
    void shiftUp(int i);
    void shiftDown(int i);
    bool better(int i, int j);
    void remove();
};
Heap::Heap() {
    heap = new int[100];
    heapSize = 0;
    capacity = 100;
}
Heap::Heap(int capacity) {
    heap = new int[capacity];
    heapSize = 0;
    this->capacity = capacity;
}
int Heap::lson(int i) {
    return i * 2 + 1;
}
int Heap::rson(int i) {
    return i * 2 + 2;
}
int Heap::parent(int i) {
    return (i - 1) / 2;
}
bool Heap::better(int i, int j) {
    return heap[i] > heap[j];
}
void Heap::shiftUp(int i) {
    if (i == 0) {
        return;
    }
    if (heap[i] > heap[parent(i)]) {
        swap(heap[i], heap[parent(i)]);
    }
    shiftUp(parent(i));
}
void Heap::shiftDown(int i) {
    int lson1 = lson(i);
    int rson1 = rson(i);
    int largest = i;
    if (lson1 < heapSize && better(heap[lson1], heap[largest])) {
        largest = lson1;
    }
    if (rson1 < heapSize && better(heap[rson1], heap[largest]))
    {
        largest = rson1;
    }
    if (largest != i) {
        swap(heap[i], heap[largest]);
        shiftDown(largest);
    }
}
void Heap::insert(int value) {
    if (heapSize >= capacity) {
        // 处理容量不足
        return;
    }
    heap[heapSize++] = value;
    shiftUp(heapSize - 1);
}
void Heap::remove() {
    if (heapSize <= 0) {
        // 处理空堆情况
        return;
    }
    swap(heap[0], heap[heapSize - 1]);
    heapSize--;
    shiftDown(0);
}
Heap::~Heap() {
    delete[] heap;
}
​
int main() {
    Heap* h = new Heap(100);
    h->insert(1);
    h->insert(2);
    h->insert(10);
    h->insert(5);
    h->insert(6);
    h->insert(7);
​
​
    for (int i = 0; i < h->heapSize; i++){
        cout<<h->heap[i]<<" ";
    }
}

算法描述

本质是在（0，n-1）找到一个最大值和第n-1个位置交换；在（0，n-2）找到一个最大值和第n-2个位置交换，反复如此，类似冒泡排序，只不过找最大值的过程，缩减成了O（lgn）的时间复杂度。

给定一个无序数组，将他原地进行递增排序

1.先建堆，把除了叶子节点外的所有元素进行下沉操作。（建堆时，我们只需从最后一个非叶子节点开始遍历，因为叶子节点没有子节点，对他们进行下沉操作没有反应，所以可以省略）

2.排序：把数组第0个元素（大顶堆中最大的元素）和数组的最后一元素进行交换，并且把堆的大小减1，然后执行”下沉“

3.把数组第0个元素和最后一个元素进行交换，并且把堆的大小减1，然后执行”下沉“

4.反复执行上述操作，最后排序成功

class Solution {
    #define eleType int
    #define idType int
    #define maxn 5000
    idType lson(idType idx){
        return idx*2+1;
    }
    idType rson(idType idx){
        return idx*2 + 2;
    }
    idType parent(idType idx){
        return (idx-1)/2;
    }
    bool better(eleType a,eleType b){
        return a>b;
    }
    void Heapify(vector<eleType>& heap,int size,eleType curr){
        idType lsonId = lson(curr);
        idType rsonId = rson(curr);
        idType optId = curr;
        if(lsonId<size&&better(heap[lsonId],heap[optId])){
            optId = lsonId;
        }
        if(rsonId<size&&better(heap[rsonId],heap[optId])){
            optId = rsonId;
        }
        if(optId!=curr){
            swap(heap[curr],heap[optId]);
            Heapify(heap,size,optId);
        }
    }
​
public:
    vector<int> sortArray(vector<int>& nums) {
        //这里从nus.size()/2开始建堆，是因为叶子节点已经满足堆了，可以直接从倒数第二层开始遍历
        for(int i = nums.size()/2;i>=0;i--){
            Heapify(nums,nums.size(),i);
        }
        //排序，将根节点与最后一个元素交换位置，这样能保证队尾永远是最大的，再将交换过去的元素进行下沉，放到他该在的地方，反复操作，最后就排好序了
        for(int i = nums.size()-1;i>=0;i--){
            swap(nums[0],nums[i]);
            Heapify(nums,i,0);
        }
        return nums;
    }
};