目錄
一.建堆的時間復(fù)雜度
1.向上調(diào)整算法建堆
2.向下調(diào)整算法建堆
二.堆排序
1.概念
2.代碼思路
3.代碼實現(xiàn)
一.建堆的時間復(fù)雜度
1.向上調(diào)整算法建堆
我們就以極端情況考慮時間復(fù)雜度(滿二叉樹+遍歷所有層)
假設(shè)所有節(jié)點個數(shù)為N,樹的高度為h
N = 2^0+2^1+2^2......+2^(h-1)
即N = 2^h - 1
h = log(N+1)
時間復(fù)雜度我們以交換次數(shù)為標(biāo)準(zhǔn)
1? ? ? ? 0
2? ? ? ? 2^0*2^1
3? ? ? ? 2^1*2^2
...
h? ? ? ?2^(h-2)*2^(h-1)
F(h) =?2^0*2^1+2^1*2^2+...+2^(h-2)*2^(h-1)
? ? ? ?= 2^h*(h-2)+2
F(N) = (N+1)(log(N+1)-2)+2(這是詳細的時間復(fù)雜度函數(shù),粗略記為O(N*logN))
2.向下調(diào)整算法建堆
1? ? ? ? (h-1)
2? ? ? ? 2^1*(h-2)
3? ? ? ? 2^2*(h-3)
...
h-1? ? 2^(h-2)*1
h? ? ? ?2^(h-1)*0
找到倒數(shù)第一個非葉節(jié)點開始向下調(diào)整
F(h) = 2^h-1-(h-1)
F(N) = N-log(N+1)(粗略記為O(N))
二.堆排序
1.概念
堆排序（Heap Sort）是一種高效的排序算法，它利用了“二叉堆”這種數(shù)據(jù)結(jié)構(gòu)來進行排序。
?
堆是一種特殊的樹狀結(jié)構(gòu)，分為最大堆和最小堆。在最大堆中，每個父節(jié)點的值都大于或等于其子節(jié)點的值；而在最小堆中，每個父節(jié)點的值都小于或等于其子節(jié)點的值。
?
堆排序的基本思想是：將待排序的序列構(gòu)建成一個最大堆，然后將最大值（即堆的根節(jié)點）與序列的最后一個元素交換位置，并將剩余元素重新構(gòu)建為一個最大堆。重復(fù)這個過程，直到整個序列有序。
?
堆排序的時間復(fù)雜度為 O(n \log n)，空間復(fù)雜度為 O(1)。它是一種不穩(wěn)定的排序算法，適用于排序整數(shù)、浮點數(shù)或其他可比較的數(shù)據(jù)類型。
?
堆排序的優(yōu)點包括：
?
1.?時間復(fù)雜度較低：堆排序的時間復(fù)雜度為 O(n \log n)，在平均情況下比其他一些排序算法（如冒泡排序、插入排序）快得多。
2.?空間復(fù)雜度低：堆排序的空間復(fù)雜度為 O(1)，它不需要額外的存儲空間來保存排序后的結(jié)果，只使用了固定的輔助空間。
3.?適用于大型數(shù)據(jù)集：堆排序可以有效地處理大型數(shù)據(jù)集，因為它的時間復(fù)雜度和空間復(fù)雜度都比較低。
?
堆排序的缺點包括：
?
1.?不穩(wěn)定：堆排序是一種不穩(wěn)定的排序算法，這意味著在排序過程中可能會改變相同值元素的相對順序。
2.?難以理解和實現(xiàn)：堆排序的概念和操作相對復(fù)雜，對于初學(xué)者來說可能比較難以理解和實現(xiàn)。
?
總的來說，堆排序是一種高效的排序算法，但在選擇排序算法時需要根據(jù)具體情況考慮其優(yōu)缺點。如果對排序的穩(wěn)定性要求較高，則可能需要選擇其他排序算法。堆排序的平均性能為O(nlogn)。它的時間復(fù)雜度和空間復(fù)雜度都比較低，適用于排序整數(shù)、浮點數(shù)或其他可比較的數(shù)據(jù)類型。
?
在最壞情況下，堆排序的時間復(fù)雜度為O(nlog2n)。因此，堆排序的平均性能較接近于最壞性能。
2.代碼思路
這里我們采用向下調(diào)整法
比如這里有一個大堆,要把它排成升序數(shù)組
?7 4 5 1 4 3
? ? ? ? ? ? ? ? s
首尾交換,把大數(shù)據(jù)放后面
?3?4 5 1 4 7
? ? ? ? ? ? ?s
讓后向下調(diào)整,把下一個大數(shù)據(jù)調(diào)到堆頂
5 4 3?1 4 7
? ? ? ? ? ? ?s
首尾交換,把大數(shù)據(jù)放后面
4 4 3?1 5?7
? ? ? ? ?s
1 4 3 4?5?7
? ? ? s
4 1?3 4?5?7
? ? ? s
3 1 4?4?5?7
? ?s
1 3?4?4?5?7文章來源：http://www.zghlxwxcb.cn/news/detail-839613.html
s文章來源地址http://www.zghlxwxcb.cn/news/detail-839613.html
3.代碼實現(xiàn)
void adjustDown(HeapDataType* p, int size, int parent)
{
int child = parent * 2 + 1;
if (p[child] < p[child + 1])
child++;
while (child <= size)
{
if (child + 1 <= size && p[parent] < p[child])
{
Swap(&p[parent], &p[child]);
parent = child;
child = child * 2 + 1;
if (p[child] < p[child + 1])
child++;
}
else break;
}
}
void heapSort(HeapDataType* p, int size)
{
//建堆,一般采用向下調(diào)整法
//向下調(diào)整法建堆的時間復(fù)雜度為O(N)
//向上調(diào)整法時間復(fù)雜度為O(N*logN)
for (int i = (size - 1 - 1) / 2; i >= 0; i--)
adjustDown(p, size, i);
//堆排序,升序用大堆,降序用小堆
while (size > 0)
{
Swap(&p[0], &p[size - 1]);
size--;
adjustDown(p, size, 0);
}
}到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)----完全二叉樹的時間復(fù)雜度講解,堆排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
