堆

一、概念

堆是一种基于完全二叉树的数据结构，当一棵完全二叉树满足下列条件时即称为堆:
每个父结点都大于等于（或者小于等于）它的两个子结点。
大于等于的情况称为大根堆，小于等于的情况称为小根堆。

完全二叉树：

• 每个结点最多有两个子结点（二叉）。
• 除了最底层，其他每一层都必须填满，最底层也需要从左到右依次填入数据。

小根堆

堆的应用：

• 构建优先队列
• 支持堆排序
• 快速找出一个集合中的最小值（或者最大值）

堆的存储：
堆的存储通过数组来实现，由于其满足完全二叉树的性质，则对于第i个结点（i从0开始算）：
父结点：(i-1)/2 // 为负数时则说明父结点不存在
左右子结点：(i * 2 + 1) 和 (i * 2 + 2)

堆的存储

二、相关操作

• 插入
  对于一个数组存储的堆，如果加入了新元素，必须想办法保持堆的特性:
  1.完全二叉。
  2.大根堆：父结点大于等于其子结点。小根堆：父结点小于等于其子结点。
  即分为两步:
  1.将新的数放入数组尾部。
  2.将最后一个数向上调整。

• 删除
  堆结构仅支持从堆顶进行删除操作，每次都能够删除最小的元素（小根堆）或者最大的元素（大根堆）。删除以后堆结构即遭到破坏（缺失了首元素），此时可以通过以下两步恢复：
  1.将最后一个元素放到堆顶。
  2.将堆顶元素向下调整。

• 堆排序
  由于堆的顶部总是最小的数（小根堆）或者最大的数（大根堆），只需要每次将顶部的数取出，然后再将堆调整为最小堆或者最大堆即可。
  取出一个数，最多需要调整logN次。有N个数需要取出，所以堆排序的时间复杂度为NlogN。

堆相关操作

三、实现

#include<stdio.h> 
#define MAX 100

int data[MAX];
int dataIndex = 0;

void swap(int parent, int pos) {
    int temp;
    temp = data[parent];
    data[parent] = data[pos];
    data[pos] = temp;
}

void fix_up() {
    int pos = dataIndex - 1;
    int value = data[pos];
    int parent = (pos - 1) / 2;

    while (parent >= 0 && value < data[parent]) {  //当前结点有父母且值小于父母
        swap(parent, pos);
        pos = parent;
        parent = (pos - 1) / 2;
        value = data[pos];
    }
}

void heap_insert(int val)
{
    data[dataIndex++] = val; //1.放到尾部
    fix_up(); //2.小根堆，向上调整
}

void fix_down(){
    if (dataIndex <= 0) {
        return;
    }
    
    int pos = 0;
    int value = data[pos];
    int left = pos * 2 + 1;
    int right = left + 1;

    while (left < dataIndex) { //左边的结点无越界 
        int refValue;
        int refPos;
        if (right < dataIndex) { //右边的结点无越界 
            refValue = data[left] < data[right] ? data[left] : data[right]; //获取子结点中较小的值 
            refPos = data[left] < data[right] ? left : right; //获取子结点中较小的值的位置 
        } else { //右边的结点有越界 
            refValue = data[left];
            refPos = left;
        }
        if (value > refValue) {
            swap(pos, refPos);
        } else {
            break;
        }
        
        pos = refPos;
        left = pos * 2 + 1;
        right = left + 1; 
        value = data[pos];
    }
}

void heap_pop() {
    if(dataIndex <= 0) {
        return;
    }
    
    data[0] = data[dataIndex - 1]; // 1.把尾部的值放到头部
    dataIndex--;
    fix_down(); // 2.小根堆，向下调整
}

void preOrder(int pos) {
    if(pos < 0 || pos > dataIndex-1) {
        return;
    }
    printf("%d ", data[pos]);
    preOrder(pos * 2 + 1);
    preOrder(pos * 2 + 2);
}

void main() {
    heap_insert(15);
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_insert(8);
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_insert(10);
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_insert(4);
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_insert(1);
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_insert(7);
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_insert(30);
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_pop();
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_pop();
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_pop();
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_pop();
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_pop();
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_pop();
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_pop();
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
    heap_pop();
    printf("preOrder: ");
    preOrder(0);
    printf("\n");
}