堆排序的思想（以最小堆為例）：
- 給的無(wú)序數(shù)列巍棱，首先要將數(shù)組改造成符合最小堆
- 關(guān)于最小堆的建造蛋欣，從最后一個(gè)非葉結(jié)點(diǎn)開(kāi)始陷虎，每個(gè)結(jié)點(diǎn)都向下調(diào)整
- 若要增加記錄杠袱，應(yīng)該加在數(shù)組的最后窝稿，然后對(duì)這個(gè)數(shù)向上調(diào)整，知直到找到合適的位置
- 若要?jiǎng)h除最小值菩彬，則只要將第一個(gè)與最后一個(gè)互換潮梯，數(shù)組長(zhǎng)度減一，從堆頂向下調(diào)整
- 若要排序耙旦，則只要從最后一個(gè)數(shù)開(kāi)始向前遍歷萝究，遍歷到的每個(gè)數(shù)與堆頂互換后從堆頂向下調(diào)整，調(diào)整時(shí)數(shù)組末尾已排序好的數(shù)字不計(jì)入操作
#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) { //向上調(diào)整只有在增加數(shù)的時(shí)候用到
int temp = nums[i];
int j = (i - 1) / 2;
while (j >= 0 && i != 0) {
if (nums[j] <= temp) { //只需比較新加入的數(shù)與父結(jié)點(diǎn)
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--) { //從最后一個(gè)非葉子結(jié)點(diǎn)開(kāi)始向下調(diào)整
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("將數(shù)組修改成最小堆:", 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);
//由于每次將最小的數(shù)放到最后，所以最小堆輸出的數(shù)組是遞增的
print("將數(shù)組排序:", nums, n);
return 0;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
