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


堆的操作
堆结构支持几种基本操作:
-
插入节点
-
根据数组构建堆
-
提取最小值节点
-
进行堆排序
鉴于堆数据结构涉及多种操作,实际应用中通常将其实现为一个类。接下来,我们将介绍如何实现这些基本功能。对于每种操作,我们还将提供相应的代码示例。
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 2if 2 * i + 1 < len(self.heap):return 1return 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) // 2if 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_elementdef _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 arraydef extract_min(self):self._swap(0, len(self.heap) - 1)min_element = self.heap.pop()self._heapify_down(0)return min_elementdef _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 2if 2 * i + 1 < len(self.heap):return 1return 0def _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) // 2if 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
如有侵权,请联系千帆社区进行删除
评论
