二叉堆
#include <stdio.h>#include <stdlib.h>/** * 经常使用 heap 实现 优先级队列 */#define MAX_SIZE 100#define True 1#define False 0typedef short Boolean;typedef struct node* pNode;struct node{int data;};pNode heap; /// index of first element is 1int size;Boolean isFull();Boolean isEmpty();void insert(pNode);pNode delete(); ///// delete the biggest nodevoid print();pNode getMax();#include "deap.h"void print(){if(isEmpty()){return;}int i = 1;while(i <= size){printf("%d ", heap->data);}printf("\n");}Boolean isFull(){if(size == MAX_SIZE+1) return True;return False;}Boolean isEmpty(){if(size == 0) {printf("Empty deap\n");return True;}return False;}// while 循环从最大堆的 新叶子结点 开始，// 沿着到根结点的路径，直到根结点// 使其父结点 i/2 的值 不小于 要插入的值void insert(pNode elem){if(isFull(size)){printf("sizeo space\n");return;}int i = ++size;while(i!=1 && elem->data > heap->data){ /// 把父结点移动到其子结点位置heap = heap;i /= 2;}heap = elem;}/// 删除根元素，然后把最后一个元素设为根元素，/// 接着进行调整，使之复合最大堆/最小堆pNode delete(){pNode res = 0;if(isEmpty()){return 0;}res = heap; /// 得到最大元素pNode last = heap; ///得到最后一个元素//heap = last;int parent = 1;//// 从新的 根元素 开始int child = 2; /// 新的根元素的 孩子while(child <= size){if(child < size && heap->data < heap->data){ ////// 比较兄弟结点，取较大者的下标child++;}if(heap->data > last->data){//// 如果 较大的子结点 大于 新的 根结点heap = heap; //// 那么把 该子结点 移动到 父结点位置parent = child; /// 当前子结点设为 起点 重新开始移动child *= 2;}else{break;}}heap = last;return res;}pNode getMax(){if(!isEmpty()){return heap;}return 0;}
页:
[1]