北京小程序开发制作公司_爱企业 查询入口_网站关键词怎么优化排名_互联网销售

堆？对于初学者来说，或许是一个陌生十足的概念。

但！堆不可怕。

什么是堆？

学术上，常常是这样说的（一个完全二叉树）。

没毛病，要想更好的理解堆(heap)，确实需要好好掌握二叉树。

但，不熟也没关系，只要掌握线性数组也能OK。

通俗的说，堆(完全二叉树)，其形状类似现实中的 "堆" (如沙堆、书堆)：

• 父节点在上，子节点在下。层次分明，如同物品层层堆叠。
• 最大堆/最小堆的性质，就是（父节点>=子节点 | 父节点<=子节点），使得其像树一样。

堆在逻辑上的操作

• 插入元素：将新元素放置在堆底，然后逐层向上调整（“向上冒泡”），保持堆的性质。
• 删除节点：将堆顶元素删除，然后将堆底元素移动到堆顶，在逐层向下调整（“向下沉底”），重新堆化。

由上图，经过观察可以发现（如：2的子节点为4和5）
总结出：在二叉树中，若当前节点的下标为 i， 则其父节点的下标为 i/2，其左子节点的下标为 i*2，其右子节点的下标为i*2+1；

最大堆：

最大堆，意思是根节点最大，往往又叫做大根堆。

• 最大堆：所有父节点的值 >= 子节点的值。

就像如图所示，完全二叉数，可以转化为数组。从而实现最大堆。

初始化最大堆的代码：

1. 定义最大堆结构体，包含指向堆数组的指针、当前元素数量和最大容量。
2. 在get_maxHeap函数中，从最后一个非叶子节点开始，对每个非叶子节点进行调整。
3. 对于每个非叶子节点，保存其值，找到左子节点。
4. 若右子节点存在且值更大，选择右子节点。
5. 若当前节点值小于子节点值，将子节点值上移，继续向下调整。
6. 找到合适位置后，将保存的值放入。

代码确实晦涩难懂些，但是跟着注释敲一遍，就确切的明白了

#include <iostream>
using namespace std;// 定义最大堆结构体
struct MaxHeap {int *heap; // 指向堆数组的指针int size;  // 当前堆中元素的数量int MaxSize; // 堆数组的最大容量
};// 初始化最大堆
void get_maxHeap(MaxHeap& maxHeap) {// 从最后一个非叶子节点开始调整堆for (int i = maxHeap.size / 2; i >= 1; i--) {int temp = maxHeap.heap[i]; // 保存当前要调整的节点的值int child = i * 2; // 找到当前节点的左子节点// 向下调整节点，直到找到合适的位置while (child <= maxHeap.size) {// 如果右子节点存在且右子节点的值更大，则选择右子节点if (child + 1 <= maxHeap.size && maxHeap.heap[child] < maxHeap.heap[child + 1]) {child++;}// 如果当前节点的值小于子节点的值，则将子节点的值上移if (temp < maxHeap.heap[child]) {maxHeap.heap[child / 2] = maxHeap.heap[child];child = child * 2; // 继续向下调整} else {break; // 找到合适的位置，退出循环}}// 将保存的节点值放入合适的位置maxHeap.heap[child / 2] = temp;}
}int main() {int heap[10] = {0, 3, 5, 6, 2, 2}; // 堆数组，下标从 1 开始MaxHeap mh;mh.heap = heap;mh.MaxSize = 10;mh.size = 5;get_maxHeap(mh); // 初始化最大堆// 输出最大堆中的元素for (int i = 1; i <= mh.size; ++i) {cout << mh.heap[i] << " ";}cout << endl;return 0;
}

本题的如下图一样变化 

        (3)/   \(5)   (6)/ \(2) (2)==========================
1、保存节点 3 的值 temp = 3。
2、找到左子节点 5 和右子节点 6，选择较大的子节点 6。
3、将 6 上移到根节点位置，3 下移到 6 的位置。
==========================(6)/   \(5)   (3)/ \(2) (2)

最大堆插入节点

最大堆的插入节点的思想就是先在堆的最后添加一个节点，然后沿着堆树上升。跟最大堆的初始化过程大致相同。

// 向最大堆中插入元素
void insert(MaxHeap& maxHeap, int val) {if (maxHeap.size == maxHeap.MaxSize) return; // 堆已满，直接返回// 先将新元素放到堆的末尾maxHeap.heap[++maxHeap.size] = val;int child = maxHeap.size;// 进行上浮操作，将新元素调整到合适的位置while (child > 1 && maxHeap.heap[child / 2] < val) {maxHeap.heap[child] = maxHeap.heap[child / 2];child = child / 2;}// 将新元素放到最终合适的位置maxHeap.heap[child] = val;
}

删除根节点

// 删除最大堆的根节点（最大值）
int deleteMax(MaxHeap& maxHeap) {if (maxHeap.size == 0) {cout << "Heap is empty!" << endl;return -1; // 表示堆为空}int maxVal = maxHeap.heap[1]; // 保存根节点的值maxHeap.heap[1] = maxHeap.heap[maxHeap.size]; // 将最后一个节点移到根节点位置maxHeap.size--; // 堆的大小减 1int i = 1; // 从根节点开始向下调整while (true) {int leftChild = 2 * i;int rightChild = 2 * i + 1;int largest = i;// 找出当前节点、左子节点和右子节点中的最大值if (leftChild <= maxHeap.size && maxHeap.heap[leftChild] > maxHeap.heap[largest]) {largest = leftChild;}if (rightChild <= maxHeap.size && maxHeap.heap[rightChild] > maxHeap.heap[largest]) {largest = rightChild;}// 如果最大值不是当前节点，则交换并继续向下调整if (largest != i) {swap(maxHeap.heap[i], maxHeap.heap[largest]);i = largest;} else {break; // 已经满足最大堆性质，退出循环}}return maxVal;
}

最小堆

最小堆，就不必咱多说了，

Ψ(￣∀￣)Ψ，就是简单的，将最大堆的操作反过来。

几种高效的排序总结：

堆排序

复杂度分析

• 时间复杂度：O(n)，其中 n 是堆中元素的数量。
• 空间复杂度：O(1)，只使用了常数级的额外空间。

将一整个数组排序的话

• 原理：利用堆这种数据结构，首先将数组构建成一个最大堆，然后依次将堆顶元素（最大值）与堆的最后一个元素交换，并调整堆，直到整个数组有序。
• 时间复杂度：无论数组初始状态如何，都需要进行 O(nlogn) 次比较和调整操作，时间复杂度始终为 O(nlogn)。

归并排序

• 原理：采用分治法，将数组分成两个子数组，分别对两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组。
• 时间复杂度：无论数组初始状态如何，都需要进行 O(nlogn) 次比较和合并操作，时间复杂度始终为 O(nlogn)。

快速排序

• 原理：选择一个基准值，将数组分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值，然后分别对左右两部分递归地进行排序。
• 时间复杂度：
  • 最坏情况：每次选择的基准值都是最大或最小的元素，时间复杂度为 O(n2)。
  • 最好情况：每次选择的基准值都能将数组均匀地分成两部分，时间复杂度为 O(nlogn)。
  • 平均情况：时间复杂度为 O(nlogn)。

截断提升 :: 基础巩固 ::

截断提升，不是一个词语，它由两部分组成。

在C++中，截断（Truncation）和提升（Promotion）是在不同的类型转换时，才会发生。

一、类型提升(Promotion)：为精度而生

为了增加数字计算的精确性。自动将较小的数据类型转换为较大类型的过程。

char c = 'A'; // ASCII值为65
int result = c + 10; // c被提升为int，结果为75

如char类型运算时，会把char类型隐式转换为int类型。

二、类型截断(Truncation)：数据丢失的风险

计算机内部，进行计算时，通常采用二进制进行计算。

数字之间储存也采用二进制储存。

如果将int类型强转为char类型，会把4位字节，截断成1位字节。

这也就意味着，强转之后，可能出现负数。

int num = 300;
char c = static_cast<char>(num); // 300的二进制为 100101100，截断后保留低8位 00101100，即十进制44

三、负数原码与补码（转换）

负数-> 原码取反+1

补码-> 取反+1

===>补码的补码 叫原码；（￣︶￣）↗　

---

借鉴博客：

1、堆的基本储存

2、数据结构堆(Heap)详解-堆的建立、插入、删除、最大堆、最小堆、堆排序等

....

---