heapSort

堆排序

#include <iostream>
#include <vector>
#include <time.h>
#include <random>
using namespace std;

void swap(vector<int> &arr, int i, int j)
{
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
void heapInsert(vector<int> &arr, int index)
{
    // 停止条件：当前来到头结点或者当前节点不在比它的父节点大
    while (arr[index] > arr[(index - 1) / 2])
    {
        swap(arr, index, (index - 1) / 2);
        index = (index - 1) / 2;
    }
}
void heapify(vector<int> &arr, int index, int heapSize)
{
    int left = index * 2 + 1;
    while (left < heapSize)
    {
        // two children choose bigger one
        int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
        // 父和较大孩子之间，谁的值大，把下标给largest
        largest = arr[largest] > arr[index] ? largest : index;
        if (index == largest)
        {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = index * 2 + 1;
    }
}
void heapSort(vector<int> &arr)
{
    if (arr.size() < 2)
    {
        return;
    }
    // O(N)
    for (int i = 0; i < arr.size(); i++)
    {
        // O(logN)
        heapInsert(arr, i);
    }
    int heapSize = arr.size();
    swap(arr, 0, --heapSize);
    // O(N)
    while (heapSize > 0)
    {
        // O(logN)
        heapify(arr, 0, heapSize);
        // O(1)
        swap(arr, 0, --heapSize);
    }
}

int main()
{
    vector<int> arr;
    srand((int)time(0));
    int left = 3, right = 99;
    for (int i = 0; i < 20; i++)
    {
        arr.push_back((int)((float)rand() / RAND_MAX * (right - left + 1) + left));
    }
    for (auto it : arr)
    {
        cout << it << " ";
    }
    cout << endl;
    heapSort(arr);
    for (auto it : arr)
    {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

小根堆

小根堆（Min Heap）是一种堆数据结构，它满足以下两个性质：

1. 父节点的值小于等于其子节点的值。

   • 对于任意节点 i，父节点的值 arr[i] <= arr[2i+1] 和 arr[i] <= arr[2i+2]。

2. 堆是一个完全二叉树或者可以看作是数组的一种逻辑结构。

   • 除了最后一层外，其他所有层都是满的，最后一层从左到右连续排列（可能不满）。
   • 堆可以使用数组来表示，根据父节点和子节点之间的关系，通过一些计算可以在数组中进行快速的定位。

小根堆的性质决定了最小的元素（根节点）位于堆的顶部。这就使得小根堆可以用来解决很多优先级相关的问题，如获取最小值或者按照升序排列元素。

小根堆的操作包括堆化和插入两个主要过程：

1. 堆化（Heapify）：

   • 堆化是将一个无序的数组转换为一个满足小根堆性质的堆的过程。
   • 堆化操作可以分为自顶向下和自底向上两种方式。
   • 自顶向下（Top-down）堆化是从根节点开始，将当前节点和其子节点进行比较并交换，直到满足小根堆性质。
   • 自底向上（Bottom-up）堆化是从最后一个非叶子节点开始，将当前节点和其子节点进行比较并交换，直到满足小根堆性质。

2. 插入（Insert）：

   • 插入操作将新元素插入到小根堆的合适位置，并保持小根堆的性质。
   • 首先，将新元素插入到数组的末尾。
   • 然后，通过比较新元素与其父节点的值，逐步向上移动元素，直到满足小根堆性质。

小根堆还可以用于优先队列的实现，其中每个元素都有一个优先级，小根堆可以快速找到具有最小优先级的元素。

堆排序算法也利用小根堆来对元素进行排序。首先，根据输入数组构建一个小根堆；然后，反复从堆顶取出最小元素，并调整堆保持小根堆性质，直到排序完成。