二叉堆(binary heap)

适用组别:提高组
难度系数:6

堆(heap):一种有特殊用途的数据结构——用来在一组变化频繁的数据集中查找最值。堆的一个经典的实现是完全二叉树(complete binary tree),

堆的特性:

  • 必须是完全二叉树
  • 任一结点的值是其子树所有结点的最大值或最小值
  • 最大值时,称为“最大堆”,也称大顶堆;
  • 最小值时,称为“最小堆”,也称小顶堆。

下面代码实现堆的建立,增减等功能

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/****************************************************************
 * C++ the implementation of a max heap
 * author: Alex Li
 * date : 2023-06-08
 * version : 1.0
 * ****************************************************************/
#include <iostream>
using namespace std;

int maxSize=15;
int heapSize;
int *arr;

int lChild(int i){
    return (2*i+1);
}

int rChild(int i){
    return (2*i+2);
}

int parent(int i){
    return(i-1)/2;
}

//to heapify the subtree.
void MaxHeapify(int i){
    int l=lChild(i);
    int r=rChild(i);
    int largest=i;
    if(l<heapSize&&arr[l]>arr[i])largest=l;
    if(r<heapSize&&arr[r]>arr[i])largest=r;
    if(largest!=i){
        swap(arr[i],arr[largest]);
        MaxHeapify(largest);
    }

}
//inserting anew key 'x'
void insertKey(int x){

    //to check whether the key can be inserted or not
    if(heapSize==maxSize){
        cout<<"\n Overflow:could not insertKey\n";
    return ; 
    }
    //the new key is initially inserted at the end;
    heapSize++;
    int i=heapSize-1;
    arr[i]=x;
    //arr[heapSize++]=x;

    //the max heap property is checked and if villation occurs, it is restored.
    while(i!=0&&arr[parent(i)]<arr[i]){
        swap(arr[i],arr[parent(i)]);
        i=parent(i);
    }

}

//increases value of key at index 'i' to  newValue
void increaseKey(int i, int newValue){
    arr[i]=newValue;
    while (i!=0&&arr[parent(i)]<arr[i]){
       swap(arr[i],arr[parent(i)]);
       i=parent(i);
    }
}

//to remove the root node which contains the maximum element of the max heap.
int removeMax(){
    if(heapSize<=0)cout<<"without element in heap.";
    if(heapSize==1){
        heapSize--;
        return arr[0];
    }

//remove the maximum element and store the last element to  heap's top
    int root=arr[0];
    arr[0]=arr[heapSize-1];
    heapSize--;
//restore the preperty of the max heap
    MaxHeapify(0);

    return root;
}

void deleteKey(int i){
//increase the value of the key to infinity and then removes the maximum value.
    increaseKey(i,INT_MAX);
    removeMax();
}


//driver function
int main(){
    arr=new int[maxSize];
    cout<<"enter some keys:\n";
    insertKey(3);
    insertKey(10);
    insertKey(12);
    insertKey(8);
    insertKey(2);
    insertKey(14);
    
    cout<<"the current size of the heap is:"<<heapSize<<'\n';
    cout<<"the current maximum element is:"<<arr[0]<<'\n';
    
    deleteKey(2);
    
    cout<<"the current size of the heap is:"<<heapSize<<'\n';

    // Inserting 2 new keys into the heap.
    insertKey(15);
    insertKey(5);
    cout<<"the current size of the heap is:"<<heapSize<<'\n';
    cout<<"the current maximum element is:"<<arr[0]<<'\n';

}
Scroll to Top