堆

堆的基础操作

堆其实就是一个完全二叉树，而完全二叉树适合用数组进行存储

基本操作：

//
// Created by zhou on 2023/10/10.
//
#include "../utils/common.h"

// 头文件functional，模板：template <class T, class Container = vector,class Compare = less >
// 小根堆
priority_queue<int, vector<int>, greater<int>> minHeap;
// 大根堆
priority_queue<int, vector<int>, less<int>> maxHeap;

void testHeap() {
    maxHeap.push(1);
    maxHeap.push(3);
    maxHeap.push(2);
    maxHeap.push(5);
    maxHeap.push(4);
    // 获取堆顶元素
    int topNum = maxHeap.top();
    // 获取大小
    int size = maxHeap.size();
    // 判断是否为空
    bool isEmpty = maxHeap.empty();
    // 出堆,会由大到小
    maxHeap.pop();
}

// 初始化建堆
vector<int> input{1, 3, 2, 4, 5};
priority_queue<int, vector<int>, less<int>> maxHeap2 (input.begin(), input.end());

利用数组模拟堆操作：

元素入堆：先插入到最尾位置，然后堆化（自底向上）

//
// Created by zhou on 2023/10/11.
//
#include "../utils/common.h"

// 利用数组模拟堆（完全二叉树）
vector<int> maxHeap;

// 封装对应的索引映射公式
int left(int i) {
    return 2 * i + 1;
}

int right(int i) {
    return 2 * i + 2;
}

int parent(int i) {
    return (i - 1) / 2;
}

/**
 * 获取堆顶元素。即数组首个元素
 */
int peek() {
    return maxHeap[0];
}

/**
 * 元素个数
 */
int size() {
    return maxHeap.size();
}

/**
 * 交换两值
 */
void swap(int &i, int &j) {
    int temp = i;
    i = j;
    j = temp;
}

/**
 * 由堆底向顶部不断堆化
 */
void siftUp(int i) {
    while (true) {
        // 先找出父节点的索引
        int parentIndex = parent(i);
        // 若是索引越界或当前插入的值并不比其父节点的值大，则无需操作，直接结束
        if (parentIndex < 0 || maxHeap[i] <= maxHeap[parentIndex]) break;
        // 比父节点的值大，需要交换
        swap(maxHeap[i], maxHeap[parentIndex]);
        // 更新索引（不断往上堆化）
        i = parentIndex;
    }
}

/**
 * 元素入堆
 * 先将新元素放堆底（即数组末尾），然后再进行堆化
 */
void push(int val) {
    int index = size() - 1;
    // 放堆底
    maxHeap[index] = val;
    // 堆化
    siftUp(index);
}

元素出堆：先把根节点元素与最尾节点元素互换，然后删除最尾元素，最后重新堆化（自上向底）

/***********************元素出堆*********************************/
/**
 * 自上向下堆化
 */
void siftDown(int i) {
    while (true) {
        // 记录左孩子索引
        int leftIndex = left(i);
        // 右孩子索引
        int rightIndex = right(i);
        // 用于记录最大值的索引
        int maxIndex = i;
        // 左孩子索引不越界且其值大于父节点的值，则先记录其索引
        if(leftIndex < size() && maxHeap[leftIndex] > maxHeap[maxIndex]) maxIndex = leftIndex;
        // 右孩子同理
        if (rightIndex < size() && maxHeap[rightIndex] > maxHeap[maxIndex]) maxIndex = rightIndex;
        // 此时maxIndex记录的就是比较后最大值的索引，若maxIndex没有变化，说明父节点就是最大值，则无需堆化。跳出循环
        if (maxIndex == i) break;
        // maxIndex值有变化，故进行交换，确保父节点的值是最大的
        swap(maxHeap[i], maxHeap[maxIndex]);
        // 向下堆化
        i = maxIndex;
    }

}

void pop() {
    if (maxHeap.empty()) return;
    // 将最尾元素与头元素互换位置
    swap(maxHeap[0], maxHeap[size() - 1]);
    // 将头元素出堆，实现元素出堆操作
    maxHeap.pop_back();
    // 自上向下堆化
    siftDown(0);
}

TOP K（返回前K大的元素）

暴力解：直接遍历K轮，每一轮都找最大元素
排序法：先排序，然后找对应的最前或最后的K个元素即可
利用小根堆：数组前K个元素先入堆，然后从第K+1个元素开始，与堆顶比较，大于堆顶的则堆顶元素出堆，新元素入堆，直至数组元素遍历完为止，此时堆中元素即为前K大的元素

//
// Created by zhou on 2023/10/11.
// 给定一个长度为 𝑛 无序数组 nums ，请返回数组中前 𝑘 大的元素。

#include "../utils//common.h"
/**
 * 求前K大元素
 * @param nums 用于初始化堆
 * @param k k个元素
 * @return 前K大的元素集合
 */
priority_queue<int, vector<int>, greater<int>> getTopK(vector<int> &nums, int k) {
    // 先声明一个堆，方便后面操作
    priority_queue<int, vector<int>, greater<int>> heap;
    // 前k个元素入堆
    for(int i = 0; i < k; i++) {
        heap.push(nums[i]);
    }
    // 从第k+1个元素开始，与堆顶元素比较，大于堆顶的则堆顶出堆，新元素入堆
    for(int i = k; i < nums.size(); i++) {
        if (nums[i] > heap.top())  {
            heap.pop();
            heap.push(nums[i]);
        }
    }
    // 最后堆中的元素即为所求
    return heap;
}