??個人主頁：個人主頁
??系列專欄：C語言試題200例
??推薦一款刷算法、筆試、面經、拿大公司offer神器?? 點擊跳轉進入網站
?作者簡介：大家好，我是碼莎拉蒂，CSDN博客專家（全站排名Top 50），阿里云博客專家、51CTO博客專家、華為云享專家

1、題目

題目：
實現堆排序算法

概念及其介紹
堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。

堆是一個近似 完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

適用說明
我們之前構造堆的過程是一個個數據調用 insert 方法使用 shift up 逐個插入到堆中，這個算法的時候時間復雜度是 O(nlogn)，本小節介紹的一種構造堆排序的過程，稱為 Heapify，算法時間復雜度為 O(n)。

過程圖示
完全二叉樹有個重要性質，對于第一個非葉子節點的索引是 n/2 取整數得到的索引值，其中 n 是元素個數(前提是數組索引從 1 開始計算)。