基本认识
-
定义：堆可以定义为一颗二叉树，树的每一个节点包含一个键，且这棵二叉树是完全二叉树，即除了最后一层，树的每一层都是满的，最后一层右边可能有缺位。
堆
由于结点左侧缺位，非堆 -
大顶堆：父节点的键值要大于或者等于子女结点的键值。
-
小顶堆：父节点的键值要小于或者等于子女结点的键值。
补充：用数组实现堆，堆并不是实际存在，认为定义的一个逻辑 ；结点n的左孩子为2n + 1，右孩子为2n + 2，结点m的父节点为(m - 1)/2
大顶堆的实现堆排序
构建大顶堆：遍历待排数组，判断每个元素与父节点元素的大小，如果孩子结点元素比父结点元素大，交换两个元素的位置，直到孩子结点元素小于等于父结点元素大小。
步骤一：结点元素位置为 i，所以元素开始比较位置index = i
步骤二：判断 index 位置（孩子元素）与 (index - 1)/2 位置（父元素）大小
a. 如果arr[index] > arr[(index-1)/2]，交换index位置与(index-1)/2位置元素， index = (index-1)/2，执行步骤二
b. 如果arr[index] <= arr[(index-1)/2]，执行步骤三
步骤三：i += 1，如果 i <= len(arr)，执行步骤二，否则，结束算法获取有序数组
步骤一：堆顶位置为 l，堆最后一个元素位置 r
步骤二：将 r 位置与 l 位置元素（堆顶位置元素，也即是最大元素）交换， r -= 1(解析：将r位置与对顶位置元素交换，那么对顶位置就会在待排数组最后位置上，即待排数组中最大元素将会被换到待排元素最后位置上，所以大于等于r位置上的元素都有序)，此时，大顶堆结构被破坏（因为堆顶位置非最大元素），待调整结点位置为 index = l
步骤三：对index结点进行调整
a. 左孩子结点位置为 left = index *2 + 1，右孩子结点位置为 left + 1
b. left <= r：如果右孩子不存在（left +1 > size）或者左孩子元素比有孩子元素大，maxIndex = left，否则maxIndex = left + 1
c. 如果arr[index] >= arr[maxIndex]，交换两个位置元素，index = maxIndex，执行步骤三，否则结束调整
d. left > r，待调整结点无孩子结点，结束调整
步骤四：如果 r >= l，执行步骤二， 否则结束算法
图解过程
-
待排数组
-
获取有序数组
代码实现
def headSort(arr):
if(len(arr) <= 1):
return
for i in range(len(arr)):
headInsert(arr, i)
r = len(arr) - 1
while(r >= 1):
arr[0], arr[r] = arr[r], arr[0]
r -= 1
heapify(arr, 0, r)
def headInsert(arr, index):
index_half = int((index - 1)/2)
while(arr[index] > arr[index_half]):
arr[index], arr[index_half] = arr[index_half], arr[index]
index = index_half
index_half = int((index - 1)/2)
def heapify(arr, l, r):
maxIndex = l
index = l
left = index * 2 + 1
while(left <= r):
maxIndex = left if (left + 1 > r) or arr[left] > arr[left + 1] else left + 1 # 判断最大值在左字树还是右子树
maxIndex = maxIndex if arr[maxIndex] > arr[index] else index
if(maxIndex == index):
break
arr[index], arr[maxIndex] = arr[maxIndex], arr[index]
index = maxIndex
left = index * 2 + 1
