#include <cstdio>
#include <cstdlib>
#define Error (-114514)
typedef int ElementType;
struct MaxHeap {
ElementType *Data;
int N;
int MaxSize;
};
bool IsEmpty(struct MaxHeap *H) {
if (H->N == 0) {
return true;
} else {
return false;
}
}
bool IsFull(struct MaxHeap *H) {
if (H->N == H->MaxSize) {
return true;
} else {
return false;
}
}
struct MaxHeap *CreatMaxHeap(int MaxSize) {
struct MaxHeap *H;
H = (struct MaxHeap *) malloc(sizeof(struct MaxHeap));
H->Data = (ElementType *) malloc(sizeof(ElementType) * MaxSize);
H->N = 0;
H->MaxSize = MaxSize;
return H;
}
ElementType FindMax(struct MaxHeap *H) {
if (IsEmpty(H)) {
return Error;
}
return H->Data[0];
}
void Insert(struct MaxHeap *H, ElementType X) {
if (IsFull(H)) {
printf("Heap is full\n");
return;
}
int i = H->N;
for (; i != 0 && H->Data[(i - 1) / 2] < X; i = (i - 1) / 2) {
H->Data[i] = H->Data[(i - 1) / 2];
}
H->Data[i] = X;
H->N++;
}
ElementType DeleteMax(struct MaxHeap *H) {
if (IsEmpty(H)) {
printf("Heap is empty.\n");
return Error;
}
int max, last_X;
int i, child;/*i是空穴下标*/
max = H->Data[0];
last_X = H->Data[H->N - 1];
H->N--;
for (i = 0; i * 2 + 1 < H->N; i = child) {
child = i * 2 + 1;/*Left child*/
if (child != H->N - 1 && H->Data[child] < H->Data[child + 1]) {//child != H->N - 1,即是防止H->Data[child + 1]数组越界，也是因为堆（特殊的完全二叉树）的性质
child++;/*Right child*/
}
if (H->Data[child] > last_X) {
H->Data[i] = H->Data[child];
} else {
break;
}
}
H->Data[i] = last_X;
return max;
}
