大根堆与小根堆

堆的本质就是以二叉树的顺序存储方式来存元素，从逻辑上看就是一颗二叉树，从结果上看是一颗完全二叉树。堆具有完全二叉树的所有性质，在次基础上规定了一系列新的规则，所以说堆就是一颗特殊的完全二叉树，但是在实际储存是通过动态数组来实现而不是类似二叉树的结点实现。

// 最大堆的结构体定义
typedef struct {
    int* heapArray;  // 存储堆元素的数组
    int capacity;    // 堆的容量
    int size;        // 堆中当前元素的个数
} MaxHeap;

// 二叉树节点的结构体定义
typedef struct TreeNode {
    int value;                 // 节点的值
    struct TreeNode* left;     // 左子节点指针
    struct TreeNode* right;    // 右子节点指针
} TreeNode;

新的规则：

大堆指所有子节点都小于他的父节点；小堆指所有子节点都大于他的父节点。

再进入代码层面之前，先回忆/预习一下相关堆性质的知识，比如大堆小堆的意义何在？大堆/小堆在每次进行数据变动的时候都会保持这么一个特性，这个特性在找到某个序列中的前某几个最大值或者最小值中起到了很好的作用，也就是堆排序。

堆排序

前面说过最大堆的性质就是一直能维护最大数到堆顶，将这个最大的数“剔出”并存起来，在代码层面就是将堆首与堆尾数值交换然后将这个最大值固定，之后再将剩下所有数再次进行堆维护，于是再次将剩下的数中的最大数也就是第二大的数与倒数第二位交换，重复此过程，最终能形成一个顺序数组。

能这样操作的一个重要前提条件就是堆的实质物理存储其实是可变数组，只是逻辑上是二叉树，所以堆排序重点在于对目标结点的索引，毕竟没有了二叉树结点的指针。

堆排序看起来很复杂，优势在哪呢？仔细看单个操作流程其实会发现很简单：

固定最大值——堆首值与左右子结点比较

固定最大值不用说，这个“比较”仔细一看其实很方便，因为堆的特性，只需要将这个值看作新插入的值，然后一直迭代向下比较就可，时间复杂度和二叉树同理，是O(树高)。

单次排序是O(树高)，那么n次排序就是O(树高*n)，算上建立堆的时间，总时间复杂度为O(nlogn)。

由于堆排序可能会导致相等元素改变相对位置，所以这种排序算法是不稳定的。

#include <iostream>
#include <vector>

void heapify(std::vector<int>& arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
if (left &lt; n &amp;&amp; arr[left] &gt; arr[largest])
    largest = left;

if (right &lt; n &amp;&amp; arr[right] &gt; arr[largest])
    largest = right;

if (largest != i) {
    std::swap(arr[i], arr[largest]);
    heapify(arr, n, largest);
}

}
void heapSort(std::vector<int>& arr) {
    int n = arr.size();
// Build heap (rearrange array)
for (int i = n / 2 - 1; i &gt;= 0; i--)
    heapify(arr, n, i);

// Extract elements from heap one by one
for (int i = n - 1; i &gt; 0; i--) {
    std::swap(arr[0], arr[i]);
    heapify(arr, i, 0);
}

}

堆化与建堆

堆化：指在已经是一个堆的基础上，对某个结点进行调整，使之能够达到堆的性质标准，分为向上堆化（上浮）和向下堆化（下沉）操作。堆化操作经常出现在堆结点增加或删除的过程中，其时间复杂度为O(logn)——堆高度
建堆：将一个无序数组或者其他数据结构转化为一个堆，是一个整体的过程，时间复杂度为O(n)

堆操作

堆在进行数据添加与数据删除的过程中，需要时刻保持堆的性质。

比较简单的操作是堆增加结点，规定直接在堆尾添加，并对其进行向上调整的堆化：

void heap_insert(vector<int>& heap, int value) {
    heap.push_back(value);  // 将新元素添加到堆的末尾
    int index = heap.size() - 1;  // 新元素的索引

while (index &gt; 0) {
    int parent_index = (index - 1) / 2;  // 父节点的索引
    if (heap[parent_index] &lt; heap[index]) {
        swap(heap[parent_index], heap[index]);  // 交换父节点和新元素
        index = parent_index;  // 更新索引为父节点的索引
    } else {
        break;
    }
}

}

堆的删除一般指删除堆顶元素，因为堆的目的就是维护一个优先队列，无论是大根堆还是小根堆，只有堆顶的元素是确定最大/最小的，所以实际运用情况一般都是删除堆顶元素，然后将堆尾元素放到堆顶，再对其进行向下调整堆化。

int heap_delete(vector<int>& heap) {
    if (heap.empty()) {
        return -1;  // 堆为空，返回一个错误值
    }

int root = heap[0];  // 堆顶元素
heap[0] = heap.back();  // 将堆的最后一个元素放到堆顶
heap.pop_back();  // 删除堆的最后一个元素
int index = 0;  // 当前节点的索引
int size = heap.size();

while (true) {
    int left_child_index = 2 * index + 1;  // 左子节点的索引
    int right_child_index = 2 * index + 2;  // 右子节点的索引
    int largest_index = index;  // 最大值的索引

    if (left_child_index &lt; size &amp;&amp; heap[left_child_index] &gt; heap[largest_index]) {
        largest_index = left_child_index;
    }

    if (right_child_index &lt; size &amp;&amp; heap[right_child_index] &gt; heap[largest_index]) {
        largest_index = right_child_index;
    }

    if (largest_index != index) {
        swap(heap[largest_index], heap[index]);  // 交换当前节点和最大值节点
        index = largest_index;
    } else {
        break;
    }
}

return root;

}

//最后有空希望能再总结一下所有常用的排序算法的性质、时间复杂度、实现方法、稳定性等

Coding中。。。

堆基础

大根堆与小根堆

堆排序

堆化与建堆

堆操作