#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
const int INF = 0x3f3f3f3f;
struct node {
int *num;
int Size; //堆的当前元素数量
int Capacity; //堆的最大容量
};
node *CreatHeap(int maxSize) {
node *maxHeap = (node *) malloc(sizeof(node));
if(!maxHeap) return NULL;
maxHeap->num = (int *) malloc(sizeof(int) * maxSize);
maxHeap->Size = 0; maxHeap->Capacity = maxSize;
maxHeap->num[0] = INF;
return maxHeap;
}
bool isFull(node *H) {
return H->Size == H->Capacity;
}
void Insert(node *maxHeap, int x) {
if(isFull(maxHeap)) {
printf("the maxHeap is FULL\n");
return ;
}
int i = ++(maxHeap->Size);
while(maxHeap->num[i/2] < x) {
maxHeap->num[i] = maxHeap->num[i/2];
i /= 2;
}
maxHeap->num[i] = x;
}
bool isEmpty(node *H) {
return H->Size == 0;
}
int DeleteMax(node *maxHeap) {
if(isEmpty(maxHeap)) {
printf("The maxHeap is Empty\n");
return -1;
}
int Maxn = maxHeap->num[1];
int tmp = maxHeap->num[(maxHeap->Size)--];
int parent, child;
for(parent = 1; parent*2 <= maxHeap->Size; parent = child) {
child = parent * 2;
if(child != maxHeap->Size &&
maxHeap->num[child] < maxHeap->num[child+1]) {
child++;
}
if(tmp >= maxHeap->num[child]) break;
else {
maxHeap->num[parent] = maxHeap->num[child];
}
}
maxHeap->num[parent] = tmp;
return Maxn;
}
int main()
{
node *maxHeap = CreatHeap(10);
for(int i = 0; i < 11; i++) {
Insert(maxHeap, i);
}
for(int i = 0; i <= maxHeap->Size; i++) {
printf("%d ", maxHeap->num[i]);
}
printf("\n");
for(int i = 0; i < 11; i++) {
printf("%d ", DeleteMax(maxHeap));
}
return 0;
}
转载请注明原文地址: https://ju.6miu.com/read-439936.html
