堆(heap)

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

但！堆不可怕。

什么是堆？

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

没毛病，要想更好的理解堆(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--; // 堆的大小减 1

    int 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)详解-堆的建立、插入、删除、最大堆、最小堆、堆排序等

....