二叉堆的插入操作
二叉堆是一种具有特定属性的二叉树，适合存储在数组中。在二叉堆中，根节点的数值最小，每个节点的数值都要小于其子节点的数值大小。这种数据结构可以用来实现一些常见的操作，如插入、删除最小值等。
下图是一个二叉堆的示例，由于二叉堆是一个完全的二叉树，所以可以用数组来表示。根节点存储在arr[0]，对任意节点i，其存储位置为arr[i]，父节点的位置为arr[(i-1)/2]，左子节点的位置为arr[2*i 1]，右子节点的位置为arr[2*i 2]。
插入操作
插入操作是将一个新的数值插入到二叉堆中的过程。首先，在二叉堆中根据完全二叉树的特性插入一个空白位置，然后将新的数值插入到空白位置。接着，需要保证父节点始终比子节点要小，如果父节点的大小大于子节点的大小，就交换父节点和子节点的值。这个过程会持续进行，直到满足二叉堆的排序特性。
插入一个新数值的时间复杂度为O(logN)，其中N是二叉堆中元素的个数。
删除最小值
删除最小值操作是指删除二叉堆的根节点。首先获取根节点的数值，然后将二叉堆的最后一个元素放到根节点的位置，然后让该元素层层下降到满足二叉堆排序特性为止。
C 代码示例
```cpp
include
using namespace std;
class MinHeap {
public:
int *arr; // 指向堆中元素的数组
int capacity; // 数组的容量
int heap_size; // 当前堆中元素的数量
public:
MinHeap(int cap);
int parent(int i) { return (i-1)/2; }
int left(int i) { return 2*i 1; }
int right(int i) { return 2*i 2; }
void insertValue(int k);
int getMin() { return arr[0]; }
void decreaseKey(int i, int new_key);
void minHeapify(int i);
int extractMin();
void deleteKey(int i);
};
// 初始化
MinHeap::MinHeap(int cap) {
capacity cap;
heap_size 0;
arr new int[cap];
}
// 插入操作
void MinHeap::insertValue(int k) {
if (heap_size capacity) {
cout << "无法插入数值" << endl;
return;
}
heap_size ;
int i heap_size - 1;
arr[i] k;
while (i ! 0 arr[parent(i)] > arr[i]) {
swap(arr[i], arr[parent(i)]);
i parent(i);
}
}
// 减小某个节点的值
void MinHeap::decreaseKey(int i, int new_key) {
arr[i] new_key;
while (i ! 0 arr[parent(i)] > arr[i]) {
swap(arr[parent(i)], arr[i]);
i parent(i);
}
}
// 维护最小堆的性质
void MinHeap::minHeapify(int i) {
int l left(i);
int r right(i);
int smallest i;
if (l < heap_size arr[l] < arr[i])
smallest l;
if (r < heap_size arr[r] < arr[smallest])
smallest r;
if (smallest ! i) {
swap(arr[i], arr[smallest
版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。
