二叉堆(binary heap)

  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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

/**************************************************************** 
 * Description: C++ the implementation of a max heap
 * Author: Alex Li
 * Date: 2023-06-08 09:47:03
 * LastEditTime: 2024-08-17 15:19:05
****************************************************************/

#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;
}

// 维护大顶堆性质，通过堆化索引为 i 的子树
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[largest]) largest = r;

    // 如果最大值不是根节点
    if (largest != i) {
        // 交换元素
        swap(arr[i], arr[largest]);

        // 递归地对受影响的子树进行堆化
        MaxHeapify(largest);
    }
}

// 向堆中插入新键
void insertKey(int x) {
    // 检查堆是否已满
    if (heapSize == maxSize) {
        cout << "\n溢出: 无法插入新键\n";
        return;
    }

    // 将新键插入到堆的末尾
    heapSize++;
    int i = heapSize - 1;
    arr[i] = x;

    // 如果堆性质被破坏，则修复堆
    while (i != 0 && arr[parent(i)] < arr[i]) {
        swap(arr[i], arr[parent(i)]);
        i = parent(i);
    }
}

// 增加索引 i 处键值为新值
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);
    }
}

// 删除堆中的根节点，即最大元素
int removeMax() {
    if (heapSize <= 0) {
        cout << "堆中没有元素。";
        return -1;
    }

    if (heapSize == 1) {
        heapSize--;
        return arr[0];
    }

    // 取出最大元素，并将堆末尾的元素放到堆顶
    int root = arr[0];
    arr[0] = arr[heapSize - 1];
    heapSize--;

    // 恢复堆的性质
    MaxHeapify(0);

    return root;
}

// 删除索引 i 处的键值
void deleteKey(int i) {
    // 将索引 i 处的值增加到无限大，然后删除最大值
    increaseKey(i, INT_MAX);
    removeMax();
}

// 主函数
int main() {
    arr = new int[maxSize];  // 分配存储堆的数组
    cout << "输入一些键值:\n";
    insertKey(3);
    insertKey(10);
    insertKey(12);
    insertKey(8);
    insertKey(2);
    insertKey(14);

    cout << "当前堆的大小是:" << heapSize << '\n';
    cout << "当前堆中的最大元素是:" << arr[0] << '\n';

    deleteKey(2);

    cout << "当前堆的大小是:" << heapSize << '\n';

    // 在堆中插入两个新键值
    insertKey(15);
    insertKey(5);
    cout << "当前堆的大小是:" << heapSize << '\n';
    cout << "当前堆中的最大元素是:" << arr[0] << '\n';

    delete[] arr;  // 释放分配的内存
}