logo

三大排序算法之堆排序

堆排序是三大排序算法系列文章的最后一篇。
堆是一种以二叉树为基础表示数组的数据结构。堆的结构遵循以下规则:
  • 完全性。堆的每一层都必须完全填充,但最后一层可以不完全填充,且填充从左侧开始。
  • 堆性质。在最小堆中,任何父节点的值都不大于其子节点的值;而在最大堆中,任何父节点的值都不小于其子节点的值。
本文将主要介绍最小堆,并提供相关示例和代码。最大堆的处理方法和最小堆类似。下面是一个最小堆的示例。

堆的操作

堆结构支持几种基本操作:
  • 插入节点
  • 根据数组构建堆
  • 提取最小值节点
  • 进行堆排序
鉴于堆数据结构涉及多种操作,实际应用中通常将其实现为一个类。接下来,我们将介绍如何实现这些基本功能。对于每种操作,我们还将提供相应的代码示例。
  
  
  
  
  
  
class Heap:
def _swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def _number_of_children(self, i):
if 2 * i + 2 < len(self.heap):
return 2
if 2 * i + 1 < len(self.heap):
return 1
return 0
  • heap 字段存储输入数组,并将其组织成堆的形式(将在后续实现)。
  • swap() 方法用于交换数组中两个指定索引的元素。
  • number_of_children() 方法用来返回一个节点的子节点数量(0、1或2)。

插入节点

在堆中插入新元素时,总是将其放置在数组的最末端。这种插入方式可能会违反堆的规则,尤其是当新元素的值小于其父节点的值时。为了解决这个问题,需要将新节点递归地向上调整,直到它满足堆的规则为止。这个过程称为“向上堆化”(heapify(up))。
例如,我们尝试在堆中插入一个值为3的节点。
  • 插入后,由于3<153 < 153<15,违反了堆的规则。因此,我们将3和15交换位置。
  • 接下来,3的新父节点是值为7的节点。由于3<73 < 73<7,依然违反堆规则,我们再次将3和7进行交换。
  • 此时,节点3位于索引2,其父节点的值为1。由于3≥13 ≥ 13≥1,满足堆的条件。这标志着插入过程的完成。
  
  
  
  
  
  
class Heap:
def insert(self, value):
self.heap.append(value)
self._heapify_up(len(self.heap) - 1)
def _heapify_up(self, i):
if i != 0:
parent_index = (i - 1) // 2
if self.heap[i] < self.heap[parent_index]:
self.swap(i, parent_index)
self._heapify_up(parent_index)
# ... #
  • insert() 方法首先将值追加到堆末尾,然后调用方法进行向上堆化处理。
  • heapify_up() 方法在堆规则不满足时,递归地对父节点进行调整,直到恢复堆的性质。

构建堆

为了构建堆,我们对输入数组的每一个元素执行插入操作。
  
  
  
  
  
  
class Heap:
def build(self, array):
self.heap = []
for value in array:
self.insert(value)
# ... #
  • build() 方法中,我们通过对传入数组中的每个元素执行插入操作来构建堆。

提取最小值节点

堆的最小节点总是位于顶部。提取这个最小节点后,我们将堆顶节点用堆尾节点替换。这会违反堆的规则,因此需要将替换上来的元素向下调整。这个算法与我们之前提到的插入操作中的向上调整类似:每一步中,我们都将当前元素与其最小的子节点交换位置。这一过程一直持续,直到堆规则得到恢复或当前元素没有子节点为止。
在上图中,值为1的节点被提取出来,而值为15的节点被放到了顶部。
  • 由于节点15违反堆规则,我们将其与它最小的子节点3交换。
  • 然后,节点15下有子节点7和8,这两个值都小于15。我们再次将15与它最小的子节点7交换。
  • 之后,节点15移至索引5,此时它只有一个子节点,即值为20的节点。由于15≤2015 ≤ 2015≤20,我们终止了向下调整的过程。
与插入时使用的堆化算法类似,此算法也具有相似的时间复杂性,执行时间为 𝑂(𝑙𝑜𝑔𝑁)
  
  
  
  
  
  
class Heap:
def extract_min(self):
self._swap(0, len(self.heap) - 1)
min_element = self.heap.pop()
self._heapify_down(0)
return min_element
def _heapify_down(self, i):
if self._number_of_children(i) == 2:
if self.heap[i] > self.heap[2 * i + 1] or self.heap[i] > self.heap[2 * i + 2]:
if self.heap[2 * i + 1] < self.heap[2 * i + 2]:
self._swap(i, 2 * i + 1)
self._heapify_down(2 * i + 1)
else:
self._swap(i, 2 * i + 2)
self._heapify_down(2 * i + 2)
elif self._number_of_children(i) == 1 and self.heap[i] > self.heap[2 * i + 1]:
self._swap(i, 2 * i + 1)
self._heapify_down(2 * i + 1)
# ... #
  
  
  
  
  
  
class Heap:
def sort(self):
array = []
while len(self.heap) > 0:
array.append(self.extract_min())
return array
# ... #

结论

我们已经讨论了堆的四种主要操作。要利用堆数据结构对数组进行排序,首先需要构建堆,然后调用排序方法。构建堆的时间复杂度为 O(N) ,而排序操作的时间复杂度为 O(N logN) ,因此,堆排序的整体时间复杂度为 O(N logN)
以下是堆类的完整实现代码。
  
  
  
  
  
  
class Heap:
def __init__(self, array):
self.build(array)
def build(self, array):
self.heap = []
for value in array:
self.insert(value)
def insert(self, value):
self.heap.append(value)
self._heapify_up(len(self.heap) - 1)
def sort(self):
array = []
while len(self.heap) > 0:
array.append(self.extract_min())
return array
def extract_min(self):
self._swap(0, len(self.heap) - 1)
min_element = self.heap.pop()
self._heapify_down(0)
return min_element
def _swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def _number_of_children(self, i):
if 2 * i + 2 < len(self.heap):
return 2
if 2 * i + 1 < len(self.heap):
return 1
return 0
def _heapify_down(self, i):
if self._number_of_children(i) == 2:
if self.heap[i] > self.heap[2 * i + 1] or self.heap[i] > self.heap[2 * i + 2]:
if self.heap[2 * i + 1] < self.heap[2 * i + 2]:
self._swap(i, 2 * i + 1)
self._heapify_down(2 * i + 1)
else:
self._swap(i, 2 * i + 2)
self._heapify_down(2 * i + 2)
elif self._number_of_children(i) == 1 and self.heap[i] > self.heap[2 * i + 1]:
self._swap(i, 2 * i + 1)
self._heapify_down(2 * i + 1)
def _heapify_up(self, i):
if i != 0:
parent_index = (i - 1) // 2
if self.heap[i] < self.heap[parent_index]:
self._swap(i, parent_index)
self._heapify_up(parent_index)
array = [14, 8, 1, 12, 6, 20, 7, 10, 18, 4, 5, 15]
heap = Heap(array)
sorted_array = heap.sort()
print(sorted_array) # [1, 4, 5, 6, 7, 8, 10, 12, 14, 15, 18, 20]
————————————————
版权声明:本文为稀土掘金博主「MobotStone」的原创文章
原文链接:https://juejin.cn/post/7357279156612956186
如有侵权,请联系千帆社区进行删除
评论
用户头像