数据结构-堆排序代码实现（详解）

**数据结构-堆排序代码实现（详解）**

堆排序是一种常见的排序算法，基于二叉堆数据结构。它首先将待排序序列构建成一个大顶堆（或小顶堆），然后反复取出堆顶元素，并将其与最后一个元素交换，重新调整堆，使得新的堆顶元素成为最大的（或最小的）。这种过程重复进行，直到整个序列有序。

**堆排序算法步骤**

1. **构建大顶堆**
* 将待排序序列中的所有元素作为二叉树的叶子结点。
* 从最后一个非叶子结点开始（即从倒数第二个结点开始），逐一调整每个结点，使得其成为大顶堆。
2. **取出堆顶元素**
* 将堆顶元素与最后一个元素交换。
3. **重新调整堆**
* 将剩余的 n-1 个元素作为二叉树，继续从最后一个非叶子结点开始，逐一调整每个结点，使得其成为大顶堆。

**堆排序代码实现**

class MaxHeap:
 def __init__(self):
 self.heap = []

 def insert(self, value):
 """向堆中插入元素"""
 self.heap.append(value)
 self._heapify_up(len(self.heap) -1)

 def _heapify_up(self, index):
 """将index位置的元素上浮到合适位置"""
 parent_index = (index -1) //2 if index >0 and self.heap[parent_index] < self.heap[index]:
 self.heap[parent_index], self.heap[index] = self.heap[index], self.heap[parent_index]
 self._heapify_up(parent_index)

 def extract_max(self):
 """取出堆顶元素"""
 if len(self.heap) ==0:
 return None if len(self.heap) ==1:
 return self.heap.pop()

 max_value = self.heap[0]
 self.heap[0] = self.heap.pop()
 self._heapify_down(0)
 return max_value def _heapify_down(self, index):
 """将index位置的元素下沉到合适位置"""
 left_child_index =2 * index +1 right_child_index =2 * index +2 largest_index = index if (
 len(self.heap) > left_child_index and self.heap[left_child_index] > self.heap[largest_index]
 ):
 largest_index = left_child_index if (
 len(self.heap) > right_child_index and self.heap[right_child_index] > self.heap[largest_index]
 ):
 largest_index = right_child_index if largest_index != index:
 self.heap[index], self.heap[largest_index] = self.heap[
 largest_index ], self.heap[index]
 self._heapify_down(largest_index)


def heap_sort(arr):
 """堆排序"""
 max_heap = MaxHeap()
 for num in arr:
 max_heap.insert(num)

 sorted_arr = []
 while max_heap.heap:
 sorted_arr.append(max_heap.extract_max())

 return sorted_arr# 测试arr = [4,2,9,6,5,1,8,3,7]
sorted_arr = heap_sort(arr)
print(sorted_arr) # 输出: [1,2,3,4,5,6,7,8,9]