在第二个步骤中,将节点6和它的两个左右节点比较大小,发现右节点最大,所以将节点6和节点9进行交换,如图所示,数组相应位置的值也交换
总结
- """ 堆排序 """
- class HeapSort:
- def __init__(self, arr):
- self.arr = arr
-
- def adjust_heap(self, i: int, n: int):
- """
- arr[i] 对应一个非叶子节点,
- adjust_heap()方法的作用就是将arr[i]这个非叶子节点下的所有子树构建成大顶堆
- 即从该非叶子节点开始,它下面的子树都满足大顶堆的定义
- 如图中的第一个非叶子节点arr[1] = 6,其对应的子树如下,构建之后变为如下
- 6 9
- =>
- 5 9 5 6
- arr=[4,6,8,5,9], i=1 => adjust_heap() => 构建之后得到arr=[4,9,8,5,6]
- 下一次再调用adjust_heap():
- arr=[4,9,8,5,6], i=0 => adjust_heap() => 构建之后得到arr=[9,6,8,5,4]
- adjust_heap()是将非叶子节点对应的
- :param i: 表示非叶子节点在数组中的索引
- :param n: 表示构建大顶堆时的元素个数(即要对多少个元素进行构建大顶堆),m是逐渐减少的
- :return:
- """
- temp = self.arr[i] # 保存非叶子节点的值
- k = 2 * i + 1 # k 为叶子结点的左子节点
- while k < n:
- # k + 1 = 2 * i + 1 + 1 = 2 * i + 2,即表示右子节点
- # self.arr[k]表示左子节点的值,self.arr[k+1]表示右子节点的值
- if k + 1 < n and self.arr[k] < self.arr[k + 1]:
- # 如果左子节点小于右子节点的值,让 k 指向右子节点
- k += 1 # => k = 2 * i + 2
- if self.arr[k] > temp: # 如果子节点(左/右子节点)大于父节点(非叶子结点)
- self.arr[i] = self.arr[k] # 把较大的值赋值给当前节点
- i = k # 让 i 指向 k 的位置
- else:
- break
- k = k * 2 + 1 # 下一个左子节点,即左子节点的左子节点
- # 当循环结束后,已经在局部将以 i 为父节点的树的最大值放在了堆顶
- self.arr[i] = temp # 将 temp 值放到调整后的位置
- """
- 以上代码请结合图来理解!!!
- """
-
- def heap_sort(self):
- """
- 讲一个数组(该数组是二叉树顺序存储之后的数组)构建为大顶堆
- :return:
- """
- print("=======堆排序=======")
- print("排序前的数组:", self.arr)
- # self.adjust_heap(1, len(self.arr))
- # print("第一次调整后的数组:", self.arr) # [4, 9, 8, 5, 6]
- # self.adjust_heap(0, len(self.arr))
- # print("第二次调整后的数组:", self.arr) # [9, 6, 8, 5, 4]
-
- n = len(self.arr)
- # 将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆
- i = n // 2 - 1 # 从第一个非叶子节点开始进行调整,即从左往右,从下往上进行
- while i >= 0:
- self.adjust_heap(i, n)
- i -= 1
- # 将堆顶元素与数组末尾元素交换,将最大元素“沉”到数组末尾
- # 重新调整堆结构,使其满足大顶堆或小顶堆的定义,然后继续交换堆顶元素与数组末尾元素
- # 反复执行直到整个序列有序
- j = n - 1
- while j > 0:
- # self.arr[0]为堆顶元素,self.arr[j]为数组末尾元素,将其交换
- temp = self.arr[j]
- self.arr[j] = self.arr[0]
- self.arr[0] = temp
- # 交换后重新调整堆结构,0表示从根节点开始,将整棵树进行调整
- self.adjust_heap(0, j)
- j -= 1
-
- print("排序后的数组:", self.arr)
-
-
-
- heap_sort = HeapSort([4, 6, 8, 5, 9])
- heap_sort.heap_sort()