堆排序的思想(以最小堆为例):
- 给的无序数列,首先要将数组改造成符合最小堆
- 关于最小堆的建造,从最后一个非叶结点开始,每个结点都向下调整
- 若要增加记录,应该加在数组的最后,然后对这个数向上调整,知直到找到合适的位置
- 若要删除最小值,则只要将第一个与最后一个互换,数组长度减一,从堆顶向下调整
- 若要排序,则只要从最后一个数开始向前遍历,遍历到的每个数与堆顶互换后从堆顶向下调整,调整时数组末尾已排序好的数字不计入操作
#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;
}