数据结构-5 堆的定义与操作

/* 堆的定义与操作 */ /* 堆的数据结构 */ typedef struct HeapNode *Heap; struct HeapNode { ElementType *Data; // 存储元素的数组 int Size; // 堆中当前元素个数 int Capacity; // 堆的最大容量 }; typedef Heap MaxHeap; // 最大堆 #define MAXDATA 100000; // 大于最大堆中的所有元素值 /* 创建最大容量为MaxSize的最大空堆 */ MaxHeap CreateMaxHeap(int MaxSize) { MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapNode)); H->Data = (ElementType *)malloc((MaxSize + 1) * sizeof(ElementType)); H->Size = 0; H->Capacity = MaxSize; H->Data[0] = MAXDATA; // 创建“哨兵”节点 return H; } /* 判断当前最大堆是否已满 */ int IsFull(MaxHeap H) { return (H->Size == H->Capacity); } /* 判断当前最大堆是否为空 */ int IsEmpty(MaxHeap H) { return (H->Size == 0); } /* 将元素X插入最大堆H，其中H->Data[0]已经定义为哨兵 */ void InsertItem(MaxHeap H, ElementType Item) { int position; if (IsFull(H)) { printf("最大堆已满，无法插入！\n"); return; } position = ++H->Size; /* 插入后堆中最后一个元素的位置 */ while ((position /= 2) && (H->Data[position / 2] < Item)) { H->Data[position] = H->Data[position / 2]; } H->Data[position] = Item; return; } /* 从最大堆H中取出键值为最大的元素，并删除一个结点 */ ElementType DeleteMax(MaxHeap H) { /* 用最大堆中最后一个元素从根结点开始向上过滤下层结点 */ int parent, child; ElementType maxItem, temp; if (IsEmpty(H)) { printf("最大堆已为空！"); return -1; } maxItem = H->Data[1]; temp = H->Data[H->Size--];/*取出删除前最大堆中的最后一个元素*/ for (parent = 1; parent * 2 <= H->Size; parent++) { child = parent * 2; if ((child != H->Size) && (H->Data[child] < H->Data[child + 1])) child++; if (H->Data[child] > temp) H->Data[parent] = H->Data[child]; else break; } H->Data[parent] = temp; return maxItem; } /*----------- 建造最大堆 -----------*/ void PercDown(MaxHeap H, int p) { /* 下滤：将H中以H->Data[p]为根的子堆调整为最大堆 */ int Parent, Child; ElementType X; X = H->Data[p]; /* 取出根结点存放的值 */ for (Parent = p; Parent * 2 <= H->Size; Parent = Child) { Child = Parent * 2; if ((Child != H->Size) && (H->Data[Child]<H->Data[Child + 1])) Child++; /* Child指向左右子结点的较大者 */ if (X >= H->Data[Child]) break; /* 找到了合适位置 */ else /* 下滤X */ H->Data[Parent] = H->Data[Child]; } H->Data[Parent] = X; } void BuildHeap(MaxHeap H) { /* 调整H->Data[]中的元素，使满足最大堆的有序性 */ /* 这里假设所有H->Size个元素已经存在H->Data[]中 */ int i; /* 从最后一个结点的父节点开始，到根结点1 */ for (i = H->Size / 2; i>0; i--) PercDown(H, i); }