数据结构-树-C语言-堆

#include <stdio.h> #include <stdlib.h> typedef struct HeapStruct *pHeap;//pHeap为结构指针，指向这个结构 struct HeapStruct { int *data; //模拟放入的数据 int size; //已存在的元素个数 int capacity; //堆容量 }; typedef pHeap MaxHeap; typedef pHeap MinHeap; #define MAXDATA 1000 #define ERROR -999 MaxHeap createHeap(int maxSize) { MaxHeap heap = (MaxHeap)malloc(sizeof(struct HeapStruct)); heap->data = (int *)malloc(++maxSize*sizeof(int)); heap->size = 0; heap->capacity = maxSize; heap->data[0] = MAXDATA; return heap; } bool isFull(MaxHeap heap) { return heap->capacity <= heap->size; } bool isEmpty(MaxHeap heap) { return heap->size == 0; } bool insert(MaxHeap heap, int item) { int i; if (isFull(heap)) { printf("Heap is Full"); return false; } i = ++heap->size; for (; heap->data[i / 2] < item;i/=2) { heap->data[i] = heap->data[i / 2]; } heap->data[i] = item; return true; } /* @program 思想为将根节点的元素删除，将最后一个元素设置为temp @program 通过循环为temp找到合适的位置插入其中 */ int deleteMax(MaxHeap heap) { int parent, child; int maxItem, temp; if (isEmpty(heap)) { printf("Heap is Empty"); return ERROR; } maxItem = heap->data[1]; temp = heap->data[heap->size--]; for (parent = 1; parent * 2 <= heap->size;parent=child) { child = parent * 2; if ((heap->data[child] < heap->data[child+1]) && child!=heap->size) { child++; } if (temp >= heap->data[child]) break; else heap->data[parent] = heap->data[child]; } heap->data[parent] = temp; return maxItem; } /* @program 将堆结构中data[p]的下方的堆结构修改为最大堆 @param heap 最大堆的结构指针 @param p */ void percDown(MaxHeap heap, int p) { int parent, child; int temp; temp = heap->data[p]; for (parent = p; parent * 2 <= heap->size; parent = child) { child = parent * 2; if ((heap->data[child] < heap->data[child + 1]) && child != heap->size) { child++;//返回的是左右子树中较大的data } if (temp >= heap->data[child]) break; else heap->data[parent] = heap->data[child]; } heap->data[parent] = temp; } void buildMaxHeap(MaxHeap heap) { for (int i = heap->size / 2; i > 0; i--) { percDown(heap, i); } }