一、堆和堆的实现
1.一般都是使用数组来实现，二叉堆（binary heap）是一颗完全二叉树，堆中某个节点的值总是不大于其父节点的值；
//创建一个容量为n-1的堆 索引从1开始int* binary_heap(int n) { int* p = (int*)malloc(n*sizeof(int)); return p;}
二、shift up操作，向最大堆中插入元素
一直和自己的父节点比较，子节点需要小于自己的父节点，不满足则向上升；
//向堆中插入元素 shift upvoid insert(int* heap, int data, int n) { if (heap_node_num + 1 > n) { printf("heap effect.\n"); return; } heap[heap_node_num+1] = data; int num = heap_node_num + 1; while (num > 1 && heap[num] > heap[num / 2]) { _swap(&heap[num], &heap[num / 2]); num /= 2; } heap_node_num++;
}
三、shift down取出元素
取出根元素，即优先级最高的元素，并将最后一个元素放在根结点； //向堆中弹出元素 //即弹出根节点 即优先级最高的数据 int pop(int* heap) { if (heap_node_num < 1)return -1; int pop_data = heap[1]; //将最后一个节点的数据放到根节点中 heap[1] = heap[heap_node_num]; //将根节点依次向子节点比较大小 先找到两个子节点中较大的节点 比较 //存在问题 没有判断左右孩子是否存在 for (int i = 1; i <= heap_node_num;) if (heap[2 * i]>heap[2 * i + 1]) { if (heap[i] < heap[2 * i]){ _swap(&heap[i], &heap[2 * i]); i *= 2; } else break; } else { if (heap[i] < heap[2 * i+1]) { _swap(&heap[i], &heap[2 * i+1]); i = 2 * i + 1; } else break; } heap_node_num--; return pop_data;}
