堆操作

/********************************
* 程序名称：堆
* 开发时间：
*******************************/
#include <iostream>
#include <cstdio>

using namespace std;

const int MAXS = 100;
 
int a[MAXS];       //堆数组 
int heap_size;     //堆大小 
//put()
void put(int x) {
    heap_size ++;          //堆尾+1 
    a[heap_size] = x;      //在堆尾部插入x
    int i = heap_size;     //当前堆指针
    int parent_i;          //父节点指针
    
    //不断堆化
    while(i > 1) {
        parent_i = i/2;    //父节点指针
        if(a[i] <= a[parent_i])    //满足大根堆，退出
            return;
        int temp = a[i];           //与父节点交换 
        a[i] = a[parent_i];
        a[parent_i] = temp;
        i = parent_i;      //父节点指针
    } 
} 

//get()
int get() {
    int top = a[1];       //获取根节点（堆顶） 
    a[1] = a[heap_size];  //将堆尾放到堆顶部
    heap_size --;
    int i = 1;                //当前指针指向堆顶
    int son_i;                //孩子节点指针
    
    while(i*2 <= heap_size) {
        son_i = i * 2;        //lchild
        //如有右孩子，且右孩子比左孩子要大，指向右孩子 
        if(son_i < heap_size && a[son_i + 1] > a[son_i]) {
            son_i ++;         //指向右孩子 
        } 
        if(a[i] >= a[son_i])  //符合大根堆性质  
            break;
        int temp = a[i];
        a[i] = a[son_i];
        a[son_i] = temp;
        
        i = son_i;
        
        return top;      //堆化完成，返回堆顶元素 
    }  
}

//把数组 i-n调整堆化
void heap(int a[], int i, int n) {
    int k;
    int temp = a[i];    //存储当前节点 
    for(k=2*i; k<=n; k*=2) {
        if(k<n && a[k] < a[k+1]) 
            k = k + 1;  //存在有节点，并且右节点笔左节点大，指向右孩子 
        if(temp > a[k]) //符合大根堆，退出 
            break;
        a[i] = a[k];    //否则交换当前节点和孩子节点的值 
        i = k;          //指向孩子节点 
    }
    a[i] = temp;       //将当前节点放在合适位置 
} 
//main() star
int main() {
    int x, count, n;
    cout << "请输入堆大小：";
    cin >> n;
    cout << "接下来请输入 " << n <<" 个数组件堆。\n"; 
    for(int i=1; i<=n; i++) {
        cin >> x;
        put(x);
    } 
    
    cout << "堆化数据：";
    for(int i=1; i<=n; i++) {
        cout << a[i] << ",";
    }
    cout << endl;
    
    cout << "从堆中取出顶素后堆化输出："
    get();
    
    cout << "堆化数据：";
    for(int i=1; i<=n; i++) {
        cout << a[i] << ",";
    }
    cout << endl;
     
    //code here
    return 0;
}

测试1：

请输入堆大小：10
接下来请输入 10 个数组件堆。
9 5 1 2 3 41 56 2 1 45
堆化数据：56,45,41,2,5,1,9,2,1,3,
从堆中取出顶素后堆化输出：堆化数据：45,3,41,2,5,1,9,2,1,3,

--------------------------------
Process exited after 13.38 seconds with return value 0
请按任意键继续. . .

测试2：

请输入堆大小：8
接下来请输入 8 个数组件堆。
6 5 4 1 2 3 8 7
堆化数据：8,7,6,5,2,3,4,1,
从堆中取出顶素后堆化输出：堆化数据：7,1,6,5,2,3,4,1,

--------------------------------
Process exited after 7.078 seconds with return value 0
请按任意键继续. . .