堆（优先队列）

//2020.12.27 代码可能有注释不够清楚的地方，请参考青岛大学周强老师的《数据结构实战》,下次复习时候我再更新代码。
#include<stdlib.h>
#include<cstdio>

using namespace std;

typedef int Elem;

/*写在最前面：我们所学的是二叉堆（用完全二叉树（数组）储存）
  但是我们还有二项堆、Fib堆，这两种堆就不是用完全二叉树实现的
  二叉堆只是prorityqueue这个结构实现的一种方式，而不是说优先队列等同于二叉堆
  priortiyqueue还能用二项堆、avl树、线段树还有二进制分组的vector实现 
*/ 
/*
堆的其他操作：
全部操作都首先要看这个堆是最大堆还是最小堆，细节上有些差异 
1.提高元素优先级:提高优先级 + percolateup(因为提高优先级之后，这个位置不合适了，向上过滤） 
2.降低元素优先级：降低优先级 + percolatedown(和提高优先级的的理由一致) 
3.删除元素（不是堆顶的元素）: 欲想让其灭亡，先让其膨胀，不是堆顶就提高它的优先级变成堆顶，那么我们的操作就变成了删除堆顶hh 
*/
struct heap{
    //暂时用int代替Elem 
    //动态分配空间 
    Elem *data;
    int capcity;
    int size;
};

typedef struct heap* Heap;

Heap initHeap(int max){
    Heap h;
    h = (Heap)malloc(sizeof(struct heap));
    //不够内存分配时候 
    if(h == 0) return NULL;
    h->data = (Elem*)malloc(sizeof(Elem)*(max+1));
    if(h->data == 0) return NULL;
    h->size = 0;
    return h;
//free自己写 
}

void printHeap(Heap h){
//为了方便查找，0号位置不放东西 
    for(int i = 1; i <= h->size; i ++){
        printf("%d ",h->data[i]);
    }    
    putchar(‘\n‘);
}

bool isEmpty(Heap h){
    return h->size == 0; 
}
bool isFull(Heap h){
    return h->capcity == h->size;
}

//建立小顶堆 
//从位置k开始向上过滤 
//向上渗透一直到堆顶为止，或者直至它的上一个元素不大于它为止 
void percolateUp(int k, Heap h){
    Elem x;
    x = h->data[k];
    //父子相比大小,最后如果到了树根，就没法再往上走了,不用再和父亲比了，父亲是0号位置
    //当然与0号位置相比可以采取“哨兵”的做法,我们这个程序不采用这样的写法 
    //另外,i是要继续用的，所以不能定义为for的局部变量 
    //循环判断条件解释:=1时为树根，小于父亲节点时候进行交换 
    int i;
    for(i = k; i > 1 && h->data[i] < h->data[i/2];i = i / 2){
        //将小于x的父亲节点数据copy到这个位置
        //我们不需要临时变量保存它，因为开头x就是临时变量 
        h->data[i] = h->data[i/2];
    }
    //出来循环有两种情况： i到了树根位置 or 父亲节点比x小
    //pps:我们当前的堆以最小堆为样例
    h->data[i] = x; 
}
//因为可能会失败，用boolean作为返回值
//插入的元素，插入的位置 
bool insertHeap(Elem x, Heap h){
    if(isFull(h)) return false;
    //size从0开始增长，可不就是++size的地方开始存放元素嘛 
    h->data[++h->size] = x;
    percolateUp(h->size, h);
    return true;
}

/*删除操作：堆顶元素为最大或者最小 所以删除显然是删除堆顶比较方便
  本测试程序中以最小堆为示例，删除最小的元素 
  考虑堆是空的时候，抛出异常 
*/
/*如果是删除堆顶这个位置，会导致堆顶空了一个位置，接着堆顶这个空位会与它的
  左儿子和右儿子进行交换，把这个空位给交换下去，导致一块地方给空了出来 
  最终会破坏掉整棵完全二叉树的结构
  （二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树） 
   那么我们可以交换最后一个元素和堆顶元素的位置，这样删除的就是最后一个元素的位置
   和堆顶的值，交换之后向下渗透就完事 
*/
 
void percolateDown(int k, Heap h){
    //向下渗透
    Elem x;
    x = h->data[k];
    /*****/
    printf("已经保存的临时变量为：%d,从x:%d开始过滤\n",h->data[k],h->data[k]);
    printf("当前h:");
    for(int i = 1; i <= h->size; i ++){
        printf("%d ",h->data[i]);
    }
    putchar(‘\n‘);
    /*****/
//没儿子 停，比儿子大 往下继续过滤，比儿子小 停止
//i需要用来查看停止位置即原先第k号元素应该放的新位置
//所以i必须是一个for外面的变量 
    int i,child;
//疑惑：i*2=h->size的时候，下面语句中child++也就是i*2+1不会越界？？？ 
    for(i=k; i*2 <= h->size; i=child){
        //先看左儿子  在下标1 2 3 4...这样的情况下，完全二叉树的左右儿子查找为i*2 i*2+1 找父节点i/2 
        child = i*2;
        //注意越界
        //判断条件解释：child不是最后一个，左儿子大于右儿子 
        /*****/
        printf("左儿子：%d，右儿子:%d\n",h->data[i*2],h->data[i*2+1]);
        /*****/
        //pps:child 左儿子 child+1就是右儿子嘛 
        //这个判断语句帮忙找出左儿子和右儿子哪个比较小 
        if(child != h->size && h->data[child] > h->data[child+1]){
            //更小的是右儿子 
            child ++; 
        }
        /****/
        printf("当前比较小的是：%d\n",h->data[child]); 
        /****/ 
        //i位置大于小儿子 小儿子往上挪 
        if(h->data[i] > h->data[child]){
            /***/
            printf("i位置元素：%d大于小儿子，小儿往上挪",h->data[i]);
            /***/
            h->data[i] = h->data[child];
        }else{
            break;
        } 
        /****/
        printf("当前h:");
        printHeap(h);
        /****/
    }
//出来以后，i到了叶节点 要么i处于比小儿子还小的位置上 
    /***/
    printf("最终i的位置为：%d\n",i);
    printf("x为：%d",x);
    /***/
    h->data[i] = x;
}

int removeHeap(Elem *px, Heap h){
    if(isEmpty(h)) return 0;
    *px = h->data[1];//堆顶
    h->data[1] = h->data[h->size];//用最后一个元素顶替上去 
    h->size --;//删除了少了一个
    percolateDown(1,h);//把堆顶向下过滤 
    return 1;
}

Heap buildHeap(Elem *a, int size, int max){
    Heap h;
    h = initHeap(max);
    //h为空 
    if(!h) return NULL;
    h->size = size;
    for(int i = 1; i <= size; i ++){
    //a是从0开始的 
        h->data[i] = a[i - 1];
        printf("a[%d]:%d\n",i-1,a[i - 1]);
        printf("h->data[%d]:%d\n",i,a[i - 1]);
    }
    //ppps:找父亲 i/2 找左节点 i*2 找右节点i*2 + 1
    //放进去之后开始调整元素的顺序
    //从什么地方开始调？最后一个有儿子的元素向下过滤
    //不停地往上找父节点进行向下过滤 将所有的树调整为最小堆 
    //最后一个元素为h->data[size],那么它的父节点就是size/2 
    for(int i = size / 2; i > 0; i --){
        percolateDown(i, h); 
    }
    return h; 
}

int main(){
    /*调试堆的代码*/ 
    Heap h;
    h = initHeap(10);
    insertHeap(20,h);
    printHeap(h);
    insertHeap(10,h);
    printHeap(h);
    insertHeap(5,h);
    printHeap(h);
    insertHeap(15,h);
    insertHeap(30,h);
    insertHeap(18,h);
    printHeap(h);
    Elem x;
    removeHeap(&x,h); 
    printf("%d\n",x);
    printHeap(h); 
    //以下为根据列表创建堆的代码
    
    /*Elem a[6] = {10, 50, 60, 5, 30, 20};
    //创建capcity为50的堆，首先将上面的六个元素放进去初始化 
    Heap h;
    h = buildHeap(a, 6, 50);
    printHeap(h); 
    for(int i = 1; i <= 6; i ++){
        printf("%d ",h->data[i]);
    } */
    return 0;
}