行业知识
[算法沉淀记录] 排序算法 —— 堆排序
2026-10-19 07:29:34
来源：互联网转载
排序算法 —— 堆排序
算法基础介绍
���排序（Heap Sort）是一种基于比较的排序算法，它利用堆这种数据结构来实现排序。堆是一种特殊的完全二叉树，其中每个节点的值都必须大于或等于（最大堆）或小于或等于（最小堆）其子节点的值。
基本概念
堆是一个近似完全二叉树的数据结构，满足任一非叶子节点的值不小于（或不大于）其左右孩子节点的值。堆通常分为最大堆和最小堆：
- 最大堆：每个节点的值都大于或等于其子节点的值。
- 最小堆：每个节点的值都小于或等于其子节点的值。
堆排序算法通过构建一个最大堆或最小堆，然后将堆顶元素（最大或最小值）与堆的最后一个元素交换，再将剩余的元素重新调整为最大堆或最小堆，如此反复，直到整个数组有序。
算法步骤
- 构建堆：将无序的输入数组转换为一个最大堆或最小堆。
- 堆排序：
- 将堆顶元素（最大或最小值）与堆的最后一个元素交换，将其移出堆。
- 调整剩余元素，使其重新成为一个最大堆或最小堆。
- 重复上述步骤，直到所有元素都被移出堆。
伪代码描述
function heapsort(array) build_max_heap(array) for end from size(array) down to 2 do swap array[1] with array[end] heap_size = heap_size - 1 sift_down(array, 1) end forend function
堆排序是一种高效的排序算法，具有以下优缺点：
优点
- 时间复杂度稳定：堆排序的时间复杂度为(O(nlog(n)))，其中n是数组的长度。这个复杂度在所有比较排序算法中是最优的，因为比较排序的最坏时间复杂度为(O(nlog(n)))。
- 空间复杂度低：堆排序是原地排序，除了常数个额外空间用于存储递归栈之外，不需要额外的内存空间。
- 不稳定的排序算法：堆排序是不稳定的排序算法，这意味着如果两个元素相等，它们的相对顺序在排序后可能会改变。
- 适用于各种数据类型：堆排序可以适用于各种数据类型，包括整数、浮点数、字符串等，只要能够为这些数据类型定义合适的比较操作。
- 易于实现：堆排序的实现相对简单，尤其是使用二叉堆的实现。
缺点
- 最坏情况性能差：虽然平均时间复杂度为(O(nlog(n)))，但在最坏情况下（输入数据完全逆序），堆排序的时间复杂度退化为(O(n^2))。
- 不稳定排序：对于某些需要稳定排序的应用场景（如数据库索引），堆排序可能不是最佳选择。
- 对内存要求高：虽然空间复杂度低，但在排序过程中，堆中的元素可能会频繁地移动，这可能导致较高的内存访问开销。
- 初始化堆的时间开销：虽然堆排序的总时间复杂度是(O(nlog(n)))，但这个复杂度是在整个排序过程中累积的。在实际应用中，构建初始堆的过程可能会占用一定的时间。
总体而言，堆排序是一个在实际应用中广泛使用的排序算法，特别是当内存使用是一个关键因素时。然而，对于需要稳定排序的应用，或者当数据已经部分有序时，可能需要考虑其他排序算法，如归并排序或快速排序
应用场景
堆排序在实际开发过程中的常见应用场景包括：
- 优先级队列：堆排序是优先级队列实现的基础。在许多编程语言中，优先级队列（或称为最小堆）就是基于堆排序原理实现的。这种数据结构允许快速插入和删除最小元素，常用于任务调度、事件处理等场景。
- 排序算法比较：在开发中，为了验证新算法的性能，开发者可能会将堆排序与其他排序算法（如快速排序、归并排序）进行比较。堆排序因其简单性和稳定性，常作为基准算法之一。
- 数据挖掘：在数据挖掘和机器学习领域，堆排序可用于处理大规模数据集的预处理步骤，如特征选择、频繁项集挖掘等。
- 文件系统：堆排序可用于文件系统的目录排序，帮助用户快速找到文件。
- 数据库索引：虽然数据库通常使用B树或B+树索引，但在某些特殊情况下，堆排序可以作为辅助算法来优化索引的构建过程。
- 缓存管理：在缓存管理系统中，堆排序可用于维护缓存数据的有序性，例如，根据最近最少使用（LRU）策略来淘汰缓存项。
- 算法教学：堆排序是计算机科学教育中常用的教学示例，用于讲解数据结构和算法的概念。
- 图形处理：在图形处理中，堆排序可用于顶点排序，以便于后续的图形操作，如生成凸包、计算几何形状的交点等。
- 游戏开发：在游戏开发中，堆排序可用于实现游戏对象的优先级处理，例如，根据对象的属性（如生命值、攻击力等）对对象进行排序。
- 网络协议：在网络协议处理中，堆排序可用于数据包的优先级处理，确保高优先级的数据包得到优先处理。
堆排序的优点，如时间复杂度的稳定性和低空间复杂度，使其在需要快速、高效处理大规模数据的场景中非常有用。然而，它的不稳定性也是一个需要注意的点，特别是在需要保持数据相对顺序的应用中。
时间复杂度
最佳情况
在最佳情况下，输入数组已经是有序的，堆排序只需要进行一次建堆操作，然后进行一次简单的调整即可完成排序。因此，最佳情况下的时间复杂度是 (O(n))。
最坏情况
在最坏情况下，输入数组是完全逆序的，需要进行 n-1 次建堆操作，并且每次调整堆都需要将堆中的元素重新排列。因此，最坏情况下的时间复杂度是 (O(n^2))。
平均情况
在平均情况下，堆排序的时间复杂度是 (O(nlog(n)))。这是因为虽然最坏情况下的时间复杂度是 (O(n^2))，但在大多数实际应用中，数据并不是完全逆序的，因此平均时间复杂度更接近于 (O(nlog(n)))。
空间复杂度
堆排序是一个原地排序算法，除了用于存储递归栈的常数空间之外，不需要额外的内存空间。因此，空间复杂度是 (O(1))。
证明
时间复杂度证明
- 建堆操作：建堆操作的时间复杂度是 (O(n))。
- 调整堆：调整堆的时间复杂度是 (O(n))。
- 排序过程：排序过程需要进行 n-1 次调整堆的操作。
综合以上，堆排序的总时间复杂度是 (O(n + (n-1) * O(n)) = O(n^2))。
空间复杂度证明
堆排序是一个原地排序算法，除了用于存储递归栈的常数空间之外，不需要额外的内存空间。因此，空间复杂度是 (O(1))。
综上所述，堆排序的时间复杂度在最佳情况下为 (O(n))，最坏情况下为 (O(n^2))，平均情况下为 (O(nlog(n)))，空间复杂度为 (O(1))。
代码实现
Python 实现
def heapify(arr, n, i): largest = i left = 2 * i + 1 right = 2 * i + 2 if left
C++ 模板实现
Java 实现
扩展阅读
堆排序的时间复杂度优化主要集中在减少建堆和调整堆的次数上。以下是一些常见的优化方法：
时间复杂度的优化方法
- 减少比较次数：通过减少不必要的比较，可以减少建堆和调整堆的时间。例如，可以使用二叉堆的路径压缩技术，在调整堆的过程中减少子节点与父节点的比较次数。
- 使用斐波那契堆：斐波那契堆是一种数据结构，它可以在O(log n)的时间内完成堆的插入、删除和合并操作。这比二叉堆的O(log n)复杂度更优。
- 延迟删除：在某些实现中，为了避免频繁地调整堆，可以延迟删除操作，直到需要的时候才进行。
- 减少调整堆的次数：通过选择合适的堆大小和调整策略，可以减少调整堆的次数。
历史上常用的堆排序的变种算法
- 斐波那契堆：斐波那契堆是一种改进的堆数据结构，它可以在O(log n)的时间内完成堆的插入、删除和合并操作，比二叉堆更优。
- 二叉堆：二叉堆是最常见的堆实现，它包括最大堆和最小堆。二叉堆的调整操作通常需要O(log n)的时间复杂度。
- 左倾堆：左倾堆是一种特殊的堆实现，它通过减少堆的平衡调整次数来优化性能。
- 二项堆：二项堆是一种特殊的堆实现，它使用二项树的性质来优化堆的插入和删除操作。
- 二叉索引堆：二叉索引堆是一种结合了二叉堆和二叉树索引的数据结构，它可以在O(log n)的时间内完成堆的插入、删除和合并操作。
这些变种算法的目的是通过优化堆的实现细节，减少堆排序的时间复杂度，使其在实际应用中更加高效。在选择堆排序的变种算法时，需要考虑数据的特点和应用场景，以确定最适合的算法。
斐波那契堆排序
斐波那契堆排序（Fibonacci Heap Sort）是一种堆排序的变种，由Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, 和Robert E. Tarjan在1986年提出。斐波那契堆是一种数据结构，它提供了一种堆操作的实现，这些操作包括插入、删除最小元素、删除最小元素的父节点等，其时间复杂度几乎都是O(log n)。
基本概念
斐波那契堆是一种堆数据结构，它支持以下操作：
- 插入：将一个元素添加到堆中。
- 删除最小元素：移除堆中的最小元素。
- 删除最小元素的父节点：移除并返回堆中与最小元素具有相同父节点的最小元素。
- 合并：将两个斐波那契堆合并成一个堆。
斐波那契堆通过减少堆的平衡调整次数来优化性能。在斐波那契堆中，插入和删除操作通常需要O(log n)的时间复杂度，而传统的二叉堆通常需要O(log n)的复杂度。
算法步骤
斐波那契堆排序的基本步骤如下：
- 初始化：创建一个空的斐波那契堆。
- 插入元素：将所有待排序的元素插入到斐波那契堆中。
- 删除最小元素：重复执行以下操作，直到堆中只剩下一个元素：
- 删除并返回堆中的最小元素。
- 将删除元素的后继节点（如果有）插入到堆中。
- 排序完成：最后剩下的元素是排序后的第一个元素。
伪代码描述
斐波那契堆排序(A) 创建一个空的斐波那契堆 对于每个元素x in A 插入(斐波那契堆, x) while 斐波那契堆中元素数量 > 1 删除并返回最小元素(斐波那契堆) 将删除元素的后继节点插入(斐波那契堆) 返回堆中剩下的元素
Python 代码实现
class FibonacciHeap: # internal node class class Node: def __init__(self, key, value): self.key = key self.value = value self.parent = self.child = self.left = self.right = None self.degree = 0 self.mark = False # function to iterate through a doubly linked list def iterate(self, head): node = stop = head flag = False while True: if node == stop and flag is True: break elif node == stop: flag = True yield node node = node.right # pointer to the head and minimum node in the root list root_list, min_node = None, None # maintain total node count in full fibonacci heap total_nodes = 0 # return min node in O(1) time def find_min(self): return self.min_node # extract (delete) the min node from the heap in O(log n) time # amortized cost analysis can be found here (http://bit.ly/1ow1Clm) def extract_min(self): z = self.min_node if z is not None: if z.child is not None: # attach child nodes to root list children = [x for x in self.iterate(z.child)] for i in range(0, len(children)): self.merge_with_root_list(children[i]) children[i].parent = None self.remove_from_root_list(z) # set new min node in heap if z == z.right: self.min_node = self.root_list = None else: self.min_node = z.right self.consolidate() self.total_nodes -= 1 return z # insert new node into the unordered root list in O(1) time # returns the node so that it can be used for decrease_key later def insert(self, key, value=None): n = self.Node(key, value) n.left = n.right = n self.merge_with_root_list(n) if self.min_node is None or n.key x.key: return None x.key = k y = x.parent if y is not None and x.key y.key: temp = x x, y = y, temp self.heap_link(y, x) A[d] = None d += 1 A[d] = x # find new min node - no need to reconstruct new root list below # because root list was iteratively changing as we were moving # nodes around in the above loop for i in range(0, len(A)): if A[i] is not None: if A[i].key 0: sorted_arr.append(heap.extract_min().key) return sorted_arr
C++模板代码实现
template class FibonacciHeap;template struct node{private: node *prev; node *next; node *child; node *parent; V value; int degree; bool marked;public: friend class FibonacciHeap; node *getPrev() { return prev; } node *getNext() { return next; } node *getChild() { return child; } node *getParent() { return parent; } V getValue() { return value; } bool isMarked() { return marked; } bool hasChildren() { return child; } bool hasParent() { return parent; }};template class FibonacciHeap{protected: node *heap;public: FibonacciHeap() { heap = _empty(); } virtual ~FibonacciHeap() { if (heap) { _deleteAll(heap); } } node *insert(V value) { node *ret = _singleton(value); heap = _merge(heap, ret); return ret; } void merge(FibonacciHeap &other) { heap = _merge(heap, other.heap); other.heap = _empty(); } bool isEmpty() { return heap == nullptr; } V getMinimum() { return heap->value; } V removeMinimum() { node *old = heap; heap = _removeMinimum(heap); V ret = old->value; delete old; return ret; } void decreaseKey(node *n, V value) { heap = _decreaseKey(heap, n, value); } node *find(V value) { return _find(heap, value); }private: node *_empty() { return nullptr; } node *_singleton(V value) { node *n = new node; n->value = value; n->prev = n->next = n; n->degree = 0; n->marked = false; n->child = nullptr; n->parent = nullptr; return n; } node *_merge(node *a, node *b) { if (a == nullptr) return b; if (b == nullptr) return a; if (a->value > b->value) { node *temp = a; a = b; b = temp; } node *an = a->next; node *bp = b->prev; a->next = b; b->prev = a; an->prev = bp; bp->next = an; return a; } void _deleteAll(node *n) { if (n != nullptr) { node *c = n; do { node *d = c; c = c->next; _deleteAll(d->child); delete d; } while (c != n); } } void _addChild(node *parent, node *child) { child->prev = child->next = child; child->parent = parent; parent->degree++; parent->child = _merge(parent->child, child); } void _unMarkAndUnParentAll(node *n) { if (n == nullptr) return; node *c = n; do { c->marked = false; c->parent = nullptr; c = c->next; } while (c != n); } node *_removeMinimum(node *n) { _unMarkAndUnParentAll(n->child); if (n->next == n) { n = n->child; } else { n->next->prev = n->prev; n->prev->next = n->next; n = _merge(n->next, n->child); } if (n == nullptr) return n; node *trees[64] = {nullptr}; while (true) { if (trees[n->degree] != nullptr) { node *t = trees[n->degree]; if (t == n) break; trees[n->degree] = nullptr; if (n->value value) { t->prev->next = t->next; t->next->prev = t->prev; _addChild(n, t); } else { t->prev->next = t->next; t->next->prev = t->prev; if (n->next == n) { t->next = t->prev = t; _addChild(t, n); n = t; } else { n->prev->next = t; n->next->prev = t; t->next = n->next; t->prev = n->prev; _addChild(t, n); n = t; } } continue; } else { trees[n->degree] = n; } n = n->next; } node *min = n; node *start = n; do { if (n->value value) min = n; n = n->next; } while (n != start); return min; } node *_cut(node *heap, node *n) { if (n->next == n) { n->parent->child = nullptr; } else { n->next->prev = n->prev; n->prev->next = n->next; n->parent->child = n->next; } n->next = n->prev = n; n->marked = false; return _merge(heap, n); } node *_decreaseKey(node *heap, node *n, V value) { if (n->value value = value; if (n->parent) { if (n->value parent->value) { heap = _cut(heap, n); node *parent = n->parent; n->parent = nullptr; while (parent != nullptr && parent->marked) { heap = _cut(heap, parent); n = parent; parent = n->parent; n->parent = nullptr; } if (parent != nullptr && parent->parent != nullptr) parent->marked = true; } } else { if (n->value value) { heap = n; } } return heap; } node *_find(node *heap, V value) { node *n = heap; if (n == nullptr) return nullptr; do { if (n->value == value) return n; node *ret = _find(n->child, value); if (ret) return ret; n = n->next; } while (n != heap); return nullptr; }};template void FibonacciHeapSort(vector &data){ FibonacciHeap heap; auto dataSize = data.size(); for (auto i = 0; i二叉堆排序
二叉堆排序是一种基于比较的排序算法，它利用二叉堆这种数据结构来进行排序。二叉堆是一种特殊的堆，它是一个近似完全二叉树，满足任一非叶子节点的值不大于或不小于其左右孩子节点的值。根据堆的这一特性，二叉堆分为最大堆和最小堆。在最大堆中，每个父节点的值都大于或等于其孩子节点的值；在最小堆中，每个父节点的值都小于或等于其孩子节点的值。
基本概念
- 二叉堆的性质：对于最大堆，每个父节点的值都大于或等于其孩子节点的值；对于最小堆，每个父节点的值都小于或等于其孩子节点的值。
- 堆的表示：通常使用数组来表示堆，对于任意节点i（假设数组从1开始索引），其左孩子为2i，右孩子为2i+1，父节点为i/2（向下取整）。
算法步骤
- 构建堆：将无序数组构造成一个最大堆（或最小堆）。
- 调整堆：将堆顶元素（最大或最小值）与数组末尾元素交换，然后调整堆，使其满足堆的性质。
- 重复调整：重复步骤2，直到堆中只剩下一个元素，此时数组已排序。
伪代码
二叉堆排序(array): 构建最大堆(array) for i = length(array) downto 2: 交换array[1]和array[i] 调整堆(array, 1, i - 1) end forend 二叉堆排序构建最大堆(array): n = length(array) for i = n/2 downto 1: 调整堆(array, i, n) end forend 构建最大堆调整堆(array, i, n): while 2*i self.heap[largest]: largest = self.left_child(i) if self.has_right_child(i) and self.heap[self.right_child(i)] > self.heap[largest]: largest = self.right_child(i) if largest != i: self.swap(i, largest) self.heapify_down(largest) def insert(self, key): self.heap.append(key) self.heapify_up(len(self.heap) - 1) def extract_max(self): if len(self.heap) == 0: return None max_value = self.heap[0] self.heap[0] = self.heap[-1] self.heap.pop() self.heapify_down(0) return max_value def build_heap(self, arr): self.heap = arr.copy() for i in range(len(self.heap) // 2, -1, -1): self.heapify_down(i) def is_empty(self): return len(self.heap) == 0 def get_max(self): if self.is_empty(): return None return self.heap[0] def __str__(self): return str(self.heap) def max_heap_sort(arr): max_heap = MaxHeap() max_heap.build_heap(arr) sorted_arr = [] while not max_heap.is_empty(): sorted_arr.append(max_heap.extract_max()) return sorted_arr[::-1] # Reverse to get ascending order
C++模板实现
#include #include #include template void maxHeapify(std::vector& arr, int i, int n) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left arr[largest]) { largest = left; } if (right arr[largest]) { largest = right; } if (largest != i) { std::swap(arr[i], arr[largest]); maxHeapify(arr, largest, n); }}template void heapSort(std::vector& arr) { int n = arr.size(); // Build max heap for (int i = n / 2 - 1; i >= 0; i--) { maxHeapify(arr, i, n); } // Extract elements from heap for (int i = n - 1; i >= 0; i--) { std::swap(arr[0], arr[i]); maxHeapify(arr, 0, i); }}这段代码首先定义了一个maxHeapify函数，用于调整堆，使其满足最大堆的性质。然后定义了heapSort函数，该函数首先构建一个最大堆，然后通过不断将堆顶元素与数组末尾元素交换并调整堆，实现了排序。最后在main函数中测试了排序算法。
二叉堆实现
template class BinaryHeap{private: vector heap; // 用于将新插入的元素上浮到正确位置 void siftUp(int index) { while (index > 0 && heap[(index - 1) / 2] heap[largest]) { largest = left; } if (right heap[largest]) { largest = right; } if (largest != index) { swap(heap[index], heap[largest]); siftDown(largest); } }public: BinaryHeap() {} // 插入元素 void insert(T value) { heap.push_back(value); siftUp(heap.size() - 1); } // 删除堆顶元素 void remove() { if (heap.empty()) { return; } heap[0] = heap.back(); heap.pop_back(); if (!heap.empty()) { siftDown(0); } } // 获取堆顶元素 T peek() const { if (heap.empty()) { throw out_of_range("Heap is empty"); } return heap[0]; } // 获取并删除顶元素 T pop() { T value = peek(); remove(); return value; } // 判断堆是否为空 bool isEmpty() const { return heap.empty(); } // 输出堆中的元素 void print() const { for (const auto &elem : heap) { cout BinaryHeap self.heap[largest]: largest = self.left_child(i) if self.has_right_child(i) and self.heap[self.right_child(i)] > self.heap[largest]: largest = self.right_child(i) if largest != i: self.swap(i, largest) self.heapify_down(largest) def insert(self, key): self.heap.append(key) self.heapify_up(len(self.heap) - 1) def extract_max(self): if len(self.heap) == 0: return None max_value = self.heap[0] self.heap[0] = self.heap[-1] self.heap.pop() self.heapify_down(0) return max_value def build_heap(self, arr): self.heap = arr.copy() for i in range(len(self.heap) // 2, -1, -1): self.heapify_down(i) def is_empty(self): return len(self.heap) == 0 def get_max(self): if self.is_empty(): return None return self.heap[0] def __str__(self): return str(self.heap) def max_heap_sort(arr): max_heap = MaxHeap() max_heap.build_heap(arr) sorted_arr = [] while not max_heap.is_empty(): sorted_arr.append(max_heap.extract_max()) return sorted_arr[::-1] # Reverse to get ascending orderclass FibonacciHeap: # internal node class class Node: def __init__(self, key, value): self.key = key self.value = value self.parent = self.child = self.left = self.right = None self.degree = 0 self.mark = False # function to iterate through a doubly linked list def iterate(self, head): node = stop = head flag = False while True: if node == stop and flag is True: break elif node == stop: flag = True yield node node = node.right # pointer to the head and minimum node in the root list root_list, min_node = None, None # maintain total node count in full fibonacci heap total_nodes = 0 # return min node in O(1) time def find_min(self): return self.min_node # extract (delete) the min node from the heap in O(log n) time # amortized cost analysis can be found here (http://bit.ly/1ow1Clm) def extract_min(self): z = self.min_node if z is not None: if z.child is not None: # attach child nodes to root list children = [x for x in self.iterate(z.child)] for i in range(0, len(children)): self.merge_with_root_list(children[i]) children[i].parent = None self.remove_from_root_list(z) # set new min node in heap if z == z.right: self.min_node = self.root_list = None else: self.min_node = z.right self.consolidate() self.total_nodes -= 1 return z # insert new node into the unordered root list in O(1) time # returns the node so that it can be used for decrease_key later def insert(self, key, value=None): n = self.Node(key, value) n.left = n.right = n self.merge_with_root_list(n) if self.min_node is None or n.key x.key: return None x.key = k y = x.parent if y is not None and x.key y.key: temp = x x, y = y, temp self.heap_link(y, x) A[d] = None d += 1 A[d] = x # find new min node - no need to reconstruct new root list below # because root list was iteratively changing as we were moving # nodes around in the above loop for i in range(0, len(A)): if A[i] is not None: if A[i].key 0: sorted_arr.append(heap.extract_min().key) return sorted_arrdef test_max_heap_sort(): data = [9, 8, 3, 7, 5, 6, 4, 1] max_heap_sort(data) print(data) d_data = [9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1] max_heap_sort(d_data) print(d_data) c_data = ['a', 'c', 'b', 'd', 'e'] max_heap_sort(c_data) print(c_data) p_data = [Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)] max_heap_sort(p_data) for person in p_data: print(person.get_name(), person.get_age(), person.get_score())def test_fibonacci_heap_sort(): data = [9, 8, 3, 7, 5, 6, 4, 1] fibonacci_heap_sort(data) print(data) d_data = [9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1] fibonacci_heap_sort(d_data) print(d_data) c_data = ['a', 'c', 'b', 'd', 'e'] fibonacci_heap_sort(c_data) print(c_data) p_data = [Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)] fibonacci_heap_sort(p_data) for person in p_data: print(person.get_name(), person.get_age(), person.get_score())if __name__ == "__main__": test_heap_sort() test_max_heap_sort() test_fibonacci_heap_sort()C++ 代码
#include #include #include #include #include #include #include #include using namespace std;class Person{public: Person() = default; ~Person() = default; Person(string name, int age, int score) { this->name = name; this->age = age; this->socre = score; } // Override the operator> for other function to use. bool operator>(const Person &other) const { // Compare the socre of two Person objects. return this->socre > other.socre; } // Override the operatorsocre == other.socre && this->age == other.age && this->name == other.name; } // Override the operator!= for other function to use. bool operator!=(const Person &other) const { // Compare the socre, age and name of two Person objects. return this->socre != other.socre || this->age != other.age || this->name != other.name; } // Override the operator // Compare the socre, age and name of two Person objects. return this-socre =(const Person &other) const { // Compare the socre, age and name of two Person objects. return this->socre >= other.socre && this->age >= other.age && this->name >= other.name; } // Now there are some get parameters function for this calss: const string &getName() const { return this->name; } int getAge() const { return this->age; } int getScore() const { return this->socre; }private: string name; int age; int socre;};template void siftDown(RandomAccessIterator start, RandomAccessIterator end, RandomAccessIterator root){ auto child = root; advance(child, distance(start, root) + 1); if (child *root) { iter_swap(root, child); siftDown(start, end, child); } }}template void makeHeap(RandomAccessIterator start, RandomAccessIterator end){ if (start != end) { auto length = distance(start, end); auto parent = start; advance(parent, (length - 2) / 2); while (true) { siftDown(start, end, parent); if (parent == start) break; --parent; } }}template void heapSort(RandomAccessIterator start, RandomAccessIterator end){ makeHeap(start, end); while (start != end) { --end; iter_swap(start, end); siftDown(start, end, start); }}void heapSortTestCase(){ vector data = {9, 8, 3, 7, 5, 6, 4, 1}; heapSort(data.begin(), data.end()); for (int i : data) { cout 9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1}; heapSort cout 'a', 'c', 'b', 'd', 'e'}; heapSort cout Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)}; heapSort cout int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left next; t->next->prev = t->prev; _addChild(n, t); } else { t->prev->next = t->next; t->next->prev = t->prev; if (n->next == n) { t->next = t->prev = t; _addChild(t, n); n = t; } else { n->prev->next = t; n->next->prev = t; t->next = n->next; t->prev = n->prev; _addChild(t, n); n = t; } } continue; } else { trees[n->degree] = n; } n = n->next; } node *min = n; node *start = n; do { if (n->value value) min = n; n = n->next; } while (n != start); return min; } node *_cut(node *heap, node *n) { if (n->next == n) { n->parent->child = nullptr; } else { n->next->prev = n->prev; n->prev->next = n->next; n->parent->child = n->next; } n->next = n->prev = n; n->marked = false; return _merge(heap, n); } node *_decreaseKey(node *heap, node *n, V value) { if (n->value value = value; if (n->parent) { if (n->value parent->value) { heap = _cut(heap, n); node *parent = n->parent; n->parent = nullptr; while (parent != nullptr && parent->marked) { heap = _cut(heap, parent); n = parent; parent = n->parent; n->parent = nullptr; } if (parent != nullptr && parent->parent != nullptr) parent->marked = true; } } else { if (n->value value) { heap = n; } } return heap; } node *_find(node *heap, V value) { node *n = heap; if (n == nullptr) return nullptr; do { if (n->value == value) return n; node *ret = _find(n->child, value); if (ret) return ret; n = n->next; } while (n != heap); return nullptr; }};class DotFibonacciHeap : public FibonacciHeap{public: void dump() { printf("digraph G {\n"); if (heap == nullptr) { printf("empty;\n}\n"); return; } printf("minimum -> \"%p\" [constraint=false];\n", heap); node *c = heap; do { _dumpChildren(c); c = c->getNext(); } while (c != heap); printf("}\n"); }private: void _dumpChildren(node *n) { printf("\"%p\" -> \"%p\" [constraint=false,arrowhead=lnormal];\n", n, n->getNext()); printf("\"%p\" -> \"%p\" [constraint=false,arrowhead=ornormal];\n", n, n->getPrev()); if (n->isMarked()) printf("\"%p\" [style=filled,fillcolor=grey];\n", n); if (n->hasParent()) { printf("\"%p\" -> \"%p\" [constraint=false,arrowhead=onormal];\n", n, n->getParent()); } printf("\"%p\" [label=%d];\n", n, n->getValue()); if (n->hasChildren()) { node *c = n->getChild(); do { printf("\"%p\" -> \"%p\";\n", n, c); _dumpChildren(c); c = c->getNext(); } while (c != n->getChild()); } }};void DotFibonacciHeapUnitTest(){ DotFibonacciHeap h; h.insert(2); h.insert(3); h.insert(1); h.insert(4); h.removeMinimum(); h.removeMinimum(); h.insert(5); h.insert(7); h.removeMinimum(); h.insert(2); node *nine = h.insert(90); h.removeMinimum(); h.removeMinimum(); h.removeMinimum(); for (int i = 0; i
上一篇：怎么使用腾讯云做服务器?
