Min-Max heap－jumakalek586的部落格

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

void print(int list[], int n);
void insert(int list[], int key, int n);
void verifyMax(int list[], int key, int pos);
void verifyMin(int list[], int key, int pos);
int deleteMin(int list[], int n);
int deleteMax(int list[], int n);

int main()
{
char manual[] = "menu: 1.insert 2.deleteMin 3.deleteMax 4.print(just reference) 5.exit op:";
int op;

int key;

int list[MAX_SIZE];
int n = 0;

while(1){
printf("%s", manual);
scanf("%d", &op);

switch(op){
case 1:
printf(" insert value:");
scanf("%d", &key);
insert(list, key, n++);
break;

case 2:
printf("Min value = %d ", deleteMin(list, n--));
break;

case 3:
printf("Max value = %d ", deleteMax(list, n--));
break;

case 4:
print(list, n);
break;

case 5:
exit(0);
}
}
return 0;
}

void insert(int list[], int key, int n)
pos {
n++;
if(n == 1){
list[1] = key;
return;
}

int parent = n/2;

int tmp = parent, level = 0;
while(tmp){
tmp>>=1;
level++;
}

if(level%2){ // parent in min level
if(key < list[parent]){
list[n] = list[parent];
verifyMin(list, key, parent);
}
else
verifyMax(list, key, n);
}
else{ // parent in max level
if(key > list[parent]){
list[n] = list[parent];
verifyMax(list, key, parent);
}
else
verifyMin(list, key, n);
}

}

void verifyMax(int list[], int key, int pos)
{
int tmp = pos;
int grandparent = pos/4;

while(grandparent){
if(key <= list[grandparent])
break;
list[tmp] = list[grandparent];
tmp = grandparent;
grandparent = grandparent/4;
}

list[tmp] = key;
}

void verifyMin(int list[], int key, int pos)
{
int tmp = pos;
int grandparent = pos/4;

while(grandparent){
if(key >= list[grandparent])
break;

list[tmp] = list[grandparent];
tmp = grandparent;
grandparent = grandparent/4;
}

list[tmp] = key;
}

int deleteMax(int list[], int n)
{
if(n < 1){
printf("Heap is empty");
return -1;
}

if(n == 1){
n = 0;
return list[1];
}

if(n == 2){
n = 1;
return list[2];
}

if(n == 3){
n = 2;
if(list[2] >= list[3]){
int maxValue = list[2];
list[2] = list[3];
return maxValue;
}
else
return list[3];
}

int maxValue, pos, tmp;

if(list[2] >= list[3]){
maxValue = list[2];
pos = 2;
tmp = list[n--];
}
else{
maxValue = list[3];
pos = 3;
tmp = list[n--];
}

while(1){
if(2*pos > n){ // no child
list[pos] = tmp;
break;
}
else{
int maxpos;
if(4*pos > n){ // no grandchildren

maxpos = list[2*pos] > list[2*pos+1] ? 2*pos : 2*pos+1;

if(list[maxpos] > tmp){
list[pos] = list[maxpos];
list[maxpos] = tmp;
}
else
list[pos] = tmp;

break;
}
else{

maxpos = 4*pos;
for(int i = maxpos+1; i<=maxpos+3 && i >= n; i++)
if(list[i] > list[maxpos])
maxpos = i;

if(list[maxpos] > tmp){
list[pos] = list[maxpos];
if(tmp < list[maxpos/2]){
int tmp2 = tmp;
tmp = list[maxpos/2];
list[maxpos/2] = tmp2;
}

pos = maxpos;
}
else{
list[pos] = tmp;
break;
}
}
}
}
return maxValue;
}

int deleteMin(int list[], int n)
{
if(n < 1){
printf("Heap is empty");
return -1;
}

int minValue = list[1];
int tmp = list[n--];

int pos = 1;
while(1){
if(2*pos > n){ // no child
list[pos] = tmp;
break;
}
else{
int minpos;
if(4*pos > n){ // no grandchildren

minpos = list[2*pos] < list[2*pos+1] ? 2*pos : 2*pos+1;

if(list[minpos] < tmp){
list[pos] = list[minpos];
list[minpos] = tmp;
}
else
list[pos] = tmp;