堆

前言

由于太久没有接触数据结构算法相关的知识了，所以以至于连堆的基本概念都忘了，在学习之后才发觉是学过的内容——所以我做下这篇笔记，一是为了自己复习，二是希望帮助到阅读这篇笔记的人

堆的定义

说到堆，一般情况下是指的二叉堆，这里介绍二叉堆的概念，n叉堆以此类推，二项堆、斐波拉契堆、配对堆、树堆等需要另行学习

n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆

k_i <= k_2i，k_i <= k_2i+1
或者
k_i >= k_2i，k_i >= k_2i+1

其中，i = 1,2,3,4…n/2

一般情况，我们把二叉堆的逻辑结构看做是一棵特殊的完全二叉树，其特殊之处就是，

每个节点的子节点都大于其父节点（小根堆/小顶堆/最小堆）；

或者，每个节点的字节点都小于其父节点（大根堆/大顶堆/最大堆）

至于为什么是要是完全二叉树，
一是因为要贴合定义，
二是因为堆一般用数组实现，完全则保证有效下标是连续的

当然了，只要符合定义都能是堆，不过看成完全二叉树会比较容易理解

堆的建立

我们手写实现一般是用一个数组来模拟树状结构

所以只需要开一个数组就可以了，至于使数据符合定义的工作先不急

int size = 1e5 + 10;
int head[size];

下标一般从1开始，因为这样一来下标为x的节点的左孩子下标为2x，右孩子下标则为2x+1

当然如果从0开始的话，则分别是2x+1和2x+2

在讨论如何进行下一步前，我们先要了解堆的常用操作，就像是栈有push和pop一般，堆的常见操作是up和down——它们都是（递归地）操作根节的

up操作

此处以小根堆为例，大根堆则需要参考down操作类比

void up (int index) {
  while (index / 2 && heap[index] < heap[index / 2]) {
        swap(heap[index], heap[index / 2]);
        index /= 2;
    }
}

应该还是比较容易理解

down操作

void down (int index) {
    int temp = index;
    if (index * 2 <= heapSize && heap[temp] > heap[index * 2])
        temp = index * 2;
 
    if (index * 2 + 1 <= heapSize && heap[temp] > heap[index * 2 + 1])
        temp = index * 2 + 1;
    
    if (temp != index) {
        swap (heap[temp], heap[index]);
        down (temp);
    }
}

如果触发了第一个if，那么第二个if的意思就是，如果左孩子比右孩子大——这里就完成了左右孩子中选择较大的一个

down操作这里需要注意，temp和index不能随意混用，如果混用的话，在第一个if处可能不会有太大影响，但是这会给第二个if造成极大的干扰

组合操作

插入一个数

heap[++ size] = x;
up(size);

求集合最小值

heap[1];

删除最小值

heap[1] = heap[size];
size --;
down(1);

删除任意值

heap[k] = heap[size];
size --;
down(1);
up(k);

修改任意值

heap[k] = x;
down(k);
up(k);

堆排序

实际上就是建立一个堆的过程

以小根堆为例说明选出最小的前m个值的过程，下面是完整代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1e6 + 10;
int n, m, heapSize;
int heap[N];

void up (int index) {
    while (index / 2 && heap[index] < heap[index / 2]) {
        swap(heap[index], heap[index / 2]);
        index /= 2;
    }

}

void down (int index) {
    int temp = index;
    if (index * 2 <= heapSize && heap[temp] > heap[index * 2])
        temp = index * 2;
    if (index * 2 + 1 <= heapSize && heap[temp] > heap[index * 2 + 1])
        temp = index * 2 + 1;
    if (temp != index) {
        swap (heap[temp], heap[index]);
        down (temp);
    }
}

int main () {
    cin >> n >> m;
    heapSize = n;
    for(int i = 1; i <= n; i ++)
        cin >> heap[i];
    for(int i = n / 2; i; i --) 
        down (i);

    while (m --) {
        cout <<  heap[1] << " ";
        heap[1] = heap[heapSize];
        heapSize --;
        down (1);
    }
     return 0;
}