#include<iostream>
using namespace std;
//堆的插入和删除
//调整小根堆
void HeapAdjust(int* nums, int idx, int n) {
nums[0] = nums[idx]; //将要调整子树的根节点暂存在nums[0]位置处
for (int i = 2 * idx;i <= n;i *= 2) {
if (i<n && nums[i]>nums[i + 1])
i++;
if (nums[i] >= nums[idx]) { //如果父节点元素大于等于最小子结点的元素则停止循环,无需再往下进行比较
break;
}
else {
nums[idx] = nums[i];
idx = i;
}
}
nums[idx] = nums[0]; //将最初子树根节点元素存放在最终idx的位置
}
//往堆中插入一个元素
void HeapInsert(int *nums,int n,int value) {
nums[n] = value; //将要插入的元素放到堆底元素的下一个位置
while (n > 1) { //不断向上进行判断父节点的元素是否大于要插入的元素,如果大于则逐步进行交换
int pre = n / 2;
if (nums[pre] <= nums[n]) { //如果父节点元素小于或等于要插入的元素,则停止往上判断
break;
}
else {
swap(nums[pre], nums[n]);
}
n /= 2;
}
}
//删除堆中一个元素
void HeapDelete(int* nums, int idx, int n) {
swap(nums[idx], nums[n]); //将要删除的元素和堆底元素进行交换
HeapAdjust(nums, idx, n - 1); //从删除位置往下开始调整堆
}
int main() {
int nums[155],n;
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> nums[i];
}
//初步建立好的小根堆为:9 17 65 32 45 78 87 53
HeapInsert(nums, n + 1, 13); //往堆中插入元素13
n++; //数组长度加1
cout << "插入元素13后的序列为:";
for (int i = 1;i <= n;i++) {
cout << nums[i] << " ";
}
cout << endl;
HeapDelete(nums, 2, n); //删除堆中元素13
n--; //数组长度减1
cout << "删除元素13后的序列为:";
for (int i = 1;i <= n;i++) {
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/weixin_47511190/article/details/120028377
内容来源于网络,如有侵权,请联系作者删除!