堆排序

堆排序的思想（以最小堆为例）：

• 给的无序数列，首先要将数组改造成符合最小堆
  • 关于最小堆的建造，从最后一个非叶结点开始，每个结点都向下调整
• 若要增加记录，应该加在数组的最后，然后对这个数向上调整，知直到找到合适的位置
• 若要删除最小值，则只要将第一个与最后一个互换，数组长度减一，从堆顶向下调整
• 若要排序，则只要从最后一个数开始向前遍历，遍历到的每个数与堆顶互换后从堆顶向下调整，调整时数组末尾已排序好的数字不计入操作

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <sstream>
using namespace std;

void heapDown(int nums[], int i, int n) {
    
    int temp = nums[i];
    int j = 2 * i + 1;
    while (j < n) {
        if (j + 1 < n && nums[j + 1] < nums[j]) {
            j = j + 1;
        }
        if (temp < nums[j]) break;
        nums[i] = nums[j];
        i = j;
        j = 2 * i + 1;
    }
    nums[i] = temp;
}

void heapUp(int nums[], int i) { //向上调整只有在增加数的时候用到
    int temp = nums[i];
    int j = (i - 1) / 2;
    while (j >= 0 && i != 0) {
        if (nums[j] <= temp) { //只需比较新加入的数与父结点
            break;
        }
        nums[i] = nums[j];
        i = j;
        j = (i - 1) / 2;
    }
    nums[i] = temp;
}

void createHeap(int nums[], int n) {
    int i;
    for (i = (n - 1) / 2; i >= 0; i--) { //从最后一个非叶子结点开始向下调整
        heapDown(nums, i, n);
    }
}

void deleteRootNum(int nums[], int n) {
    swap(nums[0], nums[n - 1]);
    heapDown(nums, 0, n - 1);
}

void addNum(int nums[], int n, int num) {
    nums[n-1] = num;
    heapUp(nums, n-1);
}

void heapSorted(int nums[], int n) {
    for (int i = n - 1; i >= 0; i--) {
        swap(nums[i], nums[0]);
        heapDown(nums, 0, i);
    }
}

void print(string str, int nums[], int n) {
    cout<<str<<endl;
    for (int i = 0; i < n; i++) {
        cout<<nums[i]<<" ";
    }
    cout<<endl;
}

int main() {
    int n = 10;
    int nums[11] = {9, 12, 17, 30, 50, 20, 60, 65, 4, 19};
    
    createHeap(nums, n);
    print("将数组修改成最小堆:", nums, n);
    
    n = n + 1;
    addNum(nums, n, 10);
    print("插入10:", nums, n);
    
    
    deleteRootNum(nums, n);
    n = n - 1;
    print("删除了最小值:", nums, n);
    
    heapSorted(nums, n);
    //由于每次将最小的数放到最后，所以最小堆输出的数组是递增的
    print("将数组排序:", nums, n);
    
    return 0;
}