本文共 1979 字，大约阅读时间需要 6 分钟。
以最大堆为例
#include#define MAX 10000using namespace std;typedef struct Heap Heap;struct Heap{ int size; int data[MAX];};//堆调整 void adjust_heap(Heap *heap, int size, int i){ int parent, child; int t = heap->data[i]; for(parent = i; 2*parent+1 < size; parent = child){ child = parent*2+1; if(child + 1 < size && heap->data[child] < heap->data[child+1]) ++child; if(t < heap->data[child]) heap->data[parent] = heap->data[child]; else break; } heap->data[parent] = t;} //建立堆（调整法） Heap create_heap(int size){ Heap heap; heap.size = size; int x; for(int i = 0; i < size; ++i){ scanf("%d",&x); heap.data[i] = x; } for(int i = heap.size/2-1; i >=0 ; --i){ adjust_heap(&heap, heap.size, i); } return heap;}void swap(int *a, int *b){ int t = *a; *a = *b; *b = t;} //堆排序 void heap_sort(Heap *heap){ for(int i = heap->size-1; i > 0 ; --i){ swap(heap->data[0], heap->data[i]); adjust_heap(heap,i,0); } } //删除 任意元素 void heap_delet_val(Heap *heap, int val){ int i; for(i = 0; i < heap->size; ++i){ if(heap->data[i] == val) break; } swap(&heap->data[i], &heap->data[heap->size-1]); --heap->size; adjust_heap(heap, heap->size, i);}//删除顶部元素 int heap_delet_max(Heap *heap){ int val = heap->data[0]; swap(heap->data[0], heap->data[heap->size-1]); --(heap->size); adjust_heap(heap, heap->size, 0); return val;}//堆插入 void heap_insert(Heap *heap, int val){ ++heap->size; heap->data[heap->size-1] = val; int i; // 判断条件 写成 i!=0 而不能写成（i-1)/2 >= 0 后者 会进入死循环 for(i = heap->size-1; i != 0 && heap->data[(i-1)/2] < val; i = (i-1)/2){ heap->data[i] = heap->data[(i-1)/2]; } heap->data[i] = val; }int main() { int n; scanf("%d",&n); Heap heap = create_heap(n); //heap_sort(&heap); int old_size = heap.size;//删除元素 输出的时候 heap->size会变化 要提前记录size for(int i = 0; i < heap.size; ++i){ //printf("size = %d",heap.size); printf("%d ",heap.data[i]); } printf("\n"); heap_insert(&heap, 5); for(int i = 0; i < heap.size; ++i){ printf("%d ",heap.data[i]); } return 0; }
转载地址：http://tmimi.baihongyu.com/