堆實際上是一棵完全二叉樹，其任何一非葉節(jié)點滿足性質(zhì)：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非葉節(jié)點的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點的關(guān)鍵字。
堆分為大頂堆和小頂堆，滿足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱為大頂堆荠雕，滿足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱為小頂堆婶博。由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的.
小頂堆
核心代碼:
func heapSort(arr:inout [Int]) {
buildMinHeap(arr: &arr) //建立堆驹闰，無序
for i in (1..<arr.count).reversed() {
swap(&arr[i], &arr[0]) // 第一個元素和第i個元素交換
minHeap(arr: &arr, count: i, index: 0) // 第一個元素不斷的調(diào)整位置
}
}
func buildMinHeap(arr:inout [Int]) {
let count:Int = arr.count
let index:Int = count/2 - 1
for i in (0...index).reversed() {
minHeap(arr: &arr, count: count-1, index: i)
}
}
func minHeap(arr:inout [Int],count:Int,index:Int) {
var parent:Int = index
var child:Int = 2*parent + 1 // 獲取左子樹節(jié)點
while child < count {
let right:Int = child + 1
// 如果右節(jié)點大于左節(jié)點定硝，則選擇右孩子節(jié)點
if right < count && arr[child] < arr[right] {
child += 1
}
// 如果父節(jié)點大于左右節(jié)點中的大值返回
if arr[parent] > arr[child] {
break;
}
if index != child {
swap(&arr[parent], &arr[child]) // 父節(jié)點下沉
}
parent = child // 選擇孩子節(jié)點作為根節(jié)點
child = child + 1
}
}
大頂堆
核心代碼:
func heapMaxSort(arr:inout [Int]) {
buildMaxHeap(arr: &arr) //建立最大堆皿桑，無序
for i in (1..<arr.count).reversed() {
swap(&arr[i], &arr[0]) // 第一個元素和第i個元素交換
maxHeap(arr: &arr, count: i, index: 0) // 第一個元素不斷的調(diào)整位置
}
}
func buildMaxHeap(arr:inout [Int]) {
let count:Int = arr.count
let index:Int = count/2 - 1
for i in (0...index).reversed() {
maxHeap(arr: &arr, count: count-1, index: i)
}
}
func maxHeap(arr:inout [Int],count:Int,index:Int) {
var parent:Int = index
var child:Int = 2*parent + 1 // 獲取左子樹節(jié)點
while child < count {
let right:Int = child + 1
// 如果右節(jié)點小于左節(jié)點，則選擇右孩子節(jié)點
if right < count && arr[child] > arr[right] {
child += 1
}
// 如果父節(jié)點小于左右節(jié)點中的大值返回
if arr[parent] < arr[child] {
break;
}
if index != child {
swap(&arr[parent], &arr[child]) // 父節(jié)點下沉
}
parent = child // 選擇孩子節(jié)點作為根節(jié)點
child = child + 1
}
}
測試代碼:
var minHeapData:[Int] = [16,7,3,20,17,8]
let heapSort:HeapSort = HeapSort()
heapSort.heapSort(arr: &minHeapData)
print("FlyElephant--小根堆結(jié)果---\(minHeapData)")
var maxHeapData:[Int] = [16,7,3,20,17,8]
heapSort.heapMaxSort(arr: &maxHeapData)
print("FlyElephant--大根堆結(jié)果---\(maxHeapData)")
