最大-最小堆 删除算法实现

#include <cmath>
#include <iostream>
using namespace std;

#define MAXSIZE 1000  //堆中最多元素数目

//定义堆得结构
struct element {
    int key;
};

element heap[MAXSIZE];

//判断节点所在层，最小层返回true
bool level(int i)
{
    double k = log((double)i)/log(2.0);
    if((int)k%2 ==0){
        return true;
    }
    else{
        return false;
    }
}

//在最大层调整，将item插入合适位置---（insert的子函数）
void max_verify(element heap[], int n, element item)
{
    int i = n;
    int parent = n/4;
    while(parent) {
        if(heap[parent].key < item.key) {
            heap[i] = heap[parent];
            i = parent;
            parent = parent/4;
        }
  else
            break;
    }
    heap[i] = item;
}

//最小层调整，将item插入合适位置---（insert的子函数）
void min_verify(element heap[], int n, element item)
{
    int i = n;
    int parent = n/4;
    while(parent) {
        if(heap[parent].key > item.key) {
            heap[i] = heap[parent];
            i = parent;
            parent = parent/4;
        }
  else
            break;
    }
    heap[i] = item;
}

//插入一个元素
void insert(element heap[], int *n, element item)
{
    (*n)++;
 //若达到堆的最大容量，直接退出
    if(*n == MAXSIZE) {
  cout<< "heap is full." << endl;
        exit(1);
    }

 //若原堆为空，则直接加入
    if(*n == 1) {
        heap[*n].key = item.key;
        return;
    }

 //普通情况的插入
    int parent = *n/2;
    switch(level(parent)) {
case true:
    if(heap[parent].key > item.key) {
        heap[*n] = heap[parent];
        min_verify(heap, parent, item);
    } else {
        max_verify(heap, *n, item);
    }
    break;
case false:
    if(heap[parent].key < item.key) {
        heap[*n] = heap[parent];
        max_verify(heap, parent, item);
    } else {
        min_verify(heap, *n,item);
    }
    break;
    }
}

//寻找子节点和后序节点中最小的节点---（del_min的子函数）
int min_grand_child(element heap[], int n, int i)
{
    int min = 2*i;
    int k[5] = {2*i+1, 4*i, 4*i+1, 4*i+2, 4*i+3};
    for(int j=0; k[j]<=n&&j<=4; ++j) {
        if(heap[k[j]].key < heap[min].key)
            min = k[j];
    }
    return min;
}

//删除最小元素，返回最小节点
element del_min(element heap[], int *n)
{
    //没有元素时，直接退出
    if(*n < 1) {
  cout << "heap is empty." << endl;
        exit(1);
    }

    //只有一个元素，直接删除
    if(*n == 1){
        return heap[(*n)--];
    }

    //一般情况的删除最小元
    element item = heap[(*n)--];

    heap[0].key = heap[1].key;
    int k, i, last = (*n)/2, parent;
    for(i=1; i<=last; ) {
        k = min_grand_child(heap, *n, i);
        if(item.key <= heap[k].key){
            break;
        }
        heap[i] = heap[k];

        if(k <= 2*i+1) {
            i = k;
            break;
        }
        parent = k/2;
        if(item.key > heap[parent].key) {
            element temp = item;
            item = heap[parent];
            heap[parent] = temp;
        }
        i = k;
    }
    heap[i] = item;
    return heap[0];
}

//寻找子节点和后序节点中最大的节点---（del_max的子函数）
int max_grand_child(element heap[], int n, int i)
{
    int max = 2*i;
    int k[5] = {2*i+1, 4*i, 4*i+1, 4*i+2, 4*i+3};
    for(int j=0; k[j]<=n&&j<=4; ++j) {
        if(heap[k[j]].key > heap[max].key)
            max = k[j];
    }
    return max;
}

//删除最大元素
element del_max(element heap[], int *n)
{
    //没有元素时，直接退出
    if(*n < 1) {
  cout << "heap is empty." << endl;
        exit(1);
    }

    //只有一个元素，直接删除
    if(*n == 1){
        return heap[(*n)--];
    }

    //一般情况的删除最大元
    element item = heap[(*n)--];

    int minpos = max_grand_child(heap, *n, 1);

    heap[0].key = heap[minpos].key;

    int k, i, last = (*n)/2, parent;
    for(i= minpos; i<=last; ) {
        k = max_grand_child(heap, *n, i);
        if(item.key >= heap[k].key){
            break;
        }
        heap[i] = heap[k];

        if(k <= 2*i+1) {
            i = k;
            break;
        }
        parent = k/2;
        if(item.key < heap[parent].key) {
            element temp = item;
            item = heap[parent];
            heap[parent] = temp;
        }
        i = k;
    }
    heap[i] = item;
    return heap[0];
}

//驱动程序
int main()
{
    int n = 0,i,size;

 //构造初始堆
 cout << "Input the capacity of the heap(no more than 1000): ";
 cin >> size;
    for( i=1; i<=size; ++i) {
        element item;
        item.key = i;
        insert(heap, &n, item);
    }

    for( i=1; i<=n; ++i)
  cout<< heap[i].key << " ";
 cout << endl;
 
    element e = del_max(heap, &n);
    for(i=1; i<=n; ++i)
  cout << heap[i].key << " ";
 cout << "\tthe maxium element is: " << e.key << endl;
 
    e = del_min(heap, &n);
    for(i=1; i<=n; ++i)
  cout << heap[i].key << " ";
 cout << "\tthe minimum element is: " << e.key << endl;
 
    return 0;
}