PostgreSQL的FSM文件,其数据结构基础是最大堆二叉树,构建/删除/插入的相关代码详见代码注释. ```C #include "heap.h" static int heap[MAX_ELEMENTS]; static int counter = 0; //交换数据 static void swap(int *i,int *j) { int tmp = *j; *j = *i; *i = tmp; } //打印堆信息 //n : 元素个数 void print_max_heap() { for(int i = 1;i <= counter;i++) { printf("item[%d] is %d\n",i,heap[i]); } } //初始化堆数组 void init_heap(int *array,int n) { for(int i=0;i < n;i++) { heap[i] = array[i]; } counter = n; } //插入到最大堆 //item : 插入的值 //*n : 堆元素个数 void insert_max_heap(int item) { if(HEAP_FULL(counter)){ return; } //整个算法思想是首先把插入的值放在堆中的最后一个位置,然后为其找到合适的位置(递归向上) int i = ++counter; //i ≠ 1是因为数组的第一个元素并没有保存堆结点 for(;(i != 1) && (item > heap[i/2]);i = i / 2){ //如果插入的值比其父节点要大,把父节点的值交互到当前节点 heap[i] = heap[i/2];//这里其实和递归操作类似，就是去找父结点 } //父节点的值比当前值要大或者已到达根节点,设置当前位置的值为要插入的值 heap[i] = item; } //删除最大堆中的元素 //*n : 堆元素个数 void delete_max_heap() { //删除最大堆,总是删除最大堆的根节点 if(HEAP_EMPTY(counter)) { return; } //算法思想 : 把最后一个元素作为根节点,然后寻找该节点在树中合适的位置 int lastone = heap[--counter]; //父节点,初始化为1 int parent = 1; for (int son=parent*2;son <= counter;son=son*2) { //删除父节点后,比较左右子节点的大小 if(son < counter && heap[son] < heap[son+1]) { //如果右子节点大于左子节点,切换到右子节点 son++; } if (lastone > heap[son]) { break;//已经比儿子要大,退出 } //把子节点移到父节点 //parent的位置就是lastone移动到的位置 heap[parent]=heap[son]; //递归,到下一层子树 parent = son; } //parent的位置就是最后一个元素所在的位置 heap[parent]=lastone;//lastone的实际位置已找到,赋值 } //构建最大堆 //n : 元素个数 //heap是初始化但未构建的数组 void build_max_heap() { for(int i = counter;i > 1;i--) { //从最后一个元素(最下层)开始遍历数组 if(heap[i] > heap[i/2]) { //子节点比父节点要大,交换父子节点 swap(&(heap[i/2]),&(heap[i])); for(int j=i*2;j < counter;j=j*2) { //递归处理子节点 if (j > counter) { break; } if(j < counter && heap[j+1] > heap[j]) { //切换至右子节点 j++; } if (heap[j] > heap[j/2]) { //如果子节点大于父节点,交换 swap(&(heap[j/2]),&(heap[j])); } }//end for#2 }//end if }//end for#1 } void build_max_heap_new() { for(int i = counter/2;i > 1;i--) { //从子节点上一层开始处理 //父节点为i int parent=i; //该节点的值 int temp=heap[parent]; for(int child=parent*2;child <=counter;child=child*2) { // if(child < counter && heap[child] < heap[child+1]) { //切换到右子节点 child++; } if(temp > heap[child]) //父节点比子节点大,退出该父节点构成的树循环 break; else { //把子节点的值放到父节点中 heap[parent] = heap[child]; } //进入到子节点,递归处理 parent = child; } //已找到该父节点合适的位置,赋值 heap[parent]=temp; }//end for#1 } ```