[算法沉淀记录] 排序算法 —— 堆排序

排序算法 —— 堆排序

算法基础介绍

堆排序(Heap Sort)是一种基于比较的排序算法,它利用堆这种数据结构来实现排序。堆是一种特殊的完全二叉树,其中每个节点的值都必须大于或等于(最大堆)或小于或等于(最小堆)其子节点的值。

基本概念

堆是一个近似完全二叉树的数据结构,满足任一非叶子节点的值不小于(或不大于)其左右孩子节点的值。堆通常分为最大堆和最小堆:

  • 最大堆:每个节点的值都大于或等于其子节点的值。
  • 最小堆:每个节点的值都小于或等于其子节点的值。

堆排序算法通过构建一个最大堆或最小堆,然后将堆顶元素(最大或最小值)与堆的最后一个元素交换,再将剩余的元素重新调整为最大堆或最小堆,如此反复,直到整个数组有序。

算法步骤

  1. 构建堆:将无序的输入数组转换为一个最大堆或最小堆。
  2. 堆排序
    • 将堆顶元素(最大或最小值)与堆的最后一个元素交换,将其移出堆。
    • 调整剩余元素,使其重新成为一个最大堆或最小堆。
    • 重复上述步骤,直到所有元素都被移出堆。

伪代码描述

function heapsort(array)build_max_heap(array)for end from size(array) down to 2 doswap array[1] with array[end]heap_size = heap_size - 1sift_down(array, 1)end for
end function

堆排序是一种高效的排序算法,具有以下优缺点:

优点

  1. 时间复杂度稳定:堆排序的时间复杂度为(O(nlog(n))),其中n是数组的长度。这个复杂度在所有比较排序算法中是最优的,因为比较排序的最坏时间复杂度为(O(nlog(n)))。
  2. 空间复杂度低:堆排序是原地排序,除了常数个额外空间用于存储递归栈之外,不需要额外的内存空间。
  3. 不稳定的排序算法:堆排序是不稳定的排序算法,这意味着如果两个元素相等,它们的相对顺序在排序后可能会改变。
  4. 适用于各种数据类型:堆排序可以适用于各种数据类型,包括整数、浮点数、字符串等,只要能够为这些数据类型定义合适的比较操作。
  5. 易于实现:堆排序的实现相对简单,尤其是使用二叉堆的实现。

缺点

  1. 最坏情况性能差:虽然平均时间复杂度为(O(nlog(n))),但在最坏情况下(输入数据完全逆序),堆排序的时间复杂度退化为(O(n^2))。
  2. 不稳定排序:对于某些需要稳定排序的应用场景(如数据库索引),堆排序可能不是最佳选择。
  3. 对内存要求高:虽然空间复杂度低,但在排序过程中,堆中的元素可能会频繁地移动,这可能导致较高的内存访问开销。
  4. 初始化堆的时间开销:虽然堆排序的总时间复杂度是(O(nlog(n))),但这个复杂度是在整个排序过程中累积的。在实际应用中,构建初始堆的过程可能会占用一定的时间。

总体而言,堆排序是一个在实际应用中广泛使用的排序算法,特别是当内存使用是一个关键因素时。然而,对于需要稳定排序的应用,或者当数据已经部分有序时,可能需要考虑其他排序算法,如归并排序或快速排序

应用场景

堆排序在实际开发过程中的常见应用场景包括:

  1. 优先级队列:堆排序是优先级队列实现的基础。在许多编程语言中,优先级队列(或称为最小堆)就是基于堆排序原理实现的。这种数据结构允许快速插入和删除最小元素,常用于任务调度、事件处理等场景。
  2. 排序算法比较:在开发中,为了验证新算法的性能,开发者可能会将堆排序与其他排序算法(如快速排序、归并排序)进行比较。堆排序因其简单性和稳定性,常作为基准算法之一。
  3. 数据挖掘:在数据挖掘和机器学习领域,堆排序可用于处理大规模数据集的预处理步骤,如特征选择、频繁项集挖掘等。
  4. 文件系统:堆排序可用于文件系统的目录排序,帮助用户快速找到文件。
  5. 数据库索引:虽然数据库通常使用B树或B+树索引,但在某些特殊情况下,堆排序可以作为辅助算法来优化索引的构建过程。
  6. 缓存管理:在缓存管理系统中,堆排序可用于维护缓存数据的有序性,例如,根据最近最少使用(LRU)策略来淘汰缓存项。
  7. 算法教学:堆排序是计算机科学教育中常用的教学示例,用于讲解数据结构和算法的概念。
  8. 图形处理:在图形处理中,堆排序可用于顶点排序,以便于后续的图形操作,如生成凸包、计算几何形状的交点等。
  9. 游戏开发:在游戏开发中,堆排序可用于实现游戏对象的优先级处理,例如,根据对象的属性(如生命值、攻击力等)对对象进行排序。
  10. 网络协议:在网络协议处理中,堆排序可用于数据包的优先级处理,确保高优先级的数据包得到优先处理。

堆排序的优点,如时间复杂度的稳定性和低空间复杂度,使其在需要快速、高效处理大规模数据的场景中非常有用。然而,它的不稳定性也是一个需要注意的点,特别是在需要保持数据相对顺序的应用中。

时间复杂度

最佳情况

在最佳情况下,输入数组已经是有序的,堆排序只需要进行一次建堆操作,然后进行一次简单的调整即可完成排序。因此,最佳情况下的时间复杂度是 (O(n))。

最坏情况

在最坏情况下,输入数组是完全逆序的,需要进行 n-1 次建堆操作,并且每次调整堆都需要将堆中的元素重新排列。因此,最坏情况下的时间复杂度是 (O(n^2))。

平均情况

在平均情况下,堆排序的时间复杂度是 (O(nlog(n)))。这是因为虽然最坏情况下的时间复杂度是 (O(n^2)),但在大多数实际应用中,数据并不是完全逆序的,因此平均时间复杂度更接近于 (O(nlog(n)))。

空间复杂度

堆排序是一个原地排序算法,除了用于存储递归栈的常数空间之外,不需要额外的内存空间。因此,空间复杂度是 (O(1))。

证明

时间复杂度证明
  1. 建堆操作:建堆操作的时间复杂度是 (O(n))。
  2. 调整堆:调整堆的时间复杂度是 (O(n))。
  3. 排序过程:排序过程需要进行 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 = ileft = 2 * i + 1right = 2 * i + 2if left < n and arr[i] < arr[left]:largest = leftif right < n and arr[largest] < arr[right]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heapsort(arr):n = len(arr)for i in range(n//2 - 1, -1, -1):heapify(arr, n, i)for i in range(n-1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)

C++ 模板实现

Java 实现

扩展阅读

堆排序的时间复杂度优化主要集中在减少建堆和调整堆的次数上。以下是一些常见的优化方法:

时间复杂度的优化方法

  1. 减少比较次数:通过减少不必要的比较,可以减少建堆和调整堆的时间。例如,可以使用二叉堆的路径压缩技术,在调整堆的过程中减少子节点与父节点的比较次数。
  2. 使用斐波那契堆:斐波那契堆是一种数据结构,它可以在O(log n)的时间内完成堆的插入、删除和合并操作。这比二叉堆的O(log n)复杂度更优。
  3. 延迟删除:在某些实现中,为了避免频繁地调整堆,可以延迟删除操作,直到需要的时候才进行。
  4. 减少调整堆的次数:通过选择合适的堆大小和调整策略,可以减少调整堆的次数。

历史上常用的堆排序的变种算法

  1. 斐波那契堆:斐波那契堆是一种改进的堆数据结构,它可以在O(log n)的时间内完成堆的插入、删除和合并操作,比二叉堆更优。
  2. 二叉堆:二叉堆是最常见的堆实现,它包括最大堆和最小堆。二叉堆的调整操作通常需要O(log n)的时间复杂度。
  3. 左倾堆:左倾堆是一种特殊的堆实现,它通过减少堆的平衡调整次数来优化性能。
  4. 二项堆:二项堆是一种特殊的堆实现,它使用二项树的性质来优化堆的插入和删除操作。
  5. 二叉索引堆:二叉索引堆是一种结合了二叉堆和二叉树索引的数据结构,它可以在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)的复杂度。
算法步骤

斐波那契堆排序的基本步骤如下:

  1. 初始化:创建一个空的斐波那契堆。
  2. 插入元素:将所有待排序的元素插入到斐波那契堆中。
  3. 删除最小元素:重复执行以下操作,直到堆中只剩下一个元素:
    • 删除并返回堆中的最小元素。
    • 将删除元素的后继节点(如果有)插入到堆中。
  4. 排序完成:最后剩下的元素是排序后的第一个元素。
伪代码描述
斐波那契堆排序(A)创建一个空的斐波那契堆对于每个元素x in A插入(斐波那契堆, x)while 斐波那契堆中元素数量 > 1删除并返回最小元素(斐波那契堆)将删除元素的后继节点插入(斐波那契堆)返回堆中剩下的元素
Python 代码实现
class FibonacciHeap:# internal node classclass Node:def __init__(self, key, value):self.key = keyself.value = valueself.parent = self.child = self.left = self.right = Noneself.degree = 0self.mark = False# function to iterate through a doubly linked listdef iterate(self, head):node = stop = headflag = Falsewhile True:if node == stop and flag is True:breakelif node == stop:flag = Trueyield nodenode = node.right# pointer to the head and minimum node in the root listroot_list, min_node = None, None# maintain total node count in full fibonacci heaptotal_nodes = 0# return min node in O(1) timedef 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_nodeif z is not None:if z.child is not None:# attach child nodes to root listchildren = [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 = Noneself.remove_from_root_list(z)# set new min node in heapif z == z.right:self.min_node = self.root_list = Noneelse:self.min_node = z.rightself.consolidate()self.total_nodes -= 1return 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 laterdef insert(self, key, value=None):n = self.Node(key, value)n.left = n.right = nself.merge_with_root_list(n)if self.min_node is None or n.key < self.min_node.key:self.min_node = nself.total_nodes += 1return n# modify the key of some node in the heap in O(1) timedef decrease_key(self, x, k):if k > x.key:return Nonex.key = ky = x.parentif y is not None and x.key < y.key:self.cut(x, y)self.cascading_cut(y)if x.key < self.min_node.key:self.min_node = x# merge two fibonacci heaps in O(1) time by concatenating the root lists# the root of the new root list becomes equal to the first list and the second# list is simply appended to the end (then the proper min node is determined)def merge(self, h2):H = FibonacciHeap()H.root_list, H.min_node = self.root_list, self.min_node# fix pointers when merging the two heapslast = h2.root_list.lefth2.root_list.left = H.root_list.leftH.root_list.left.right = h2.root_listH.root_list.left = lastH.root_list.left.right = H.root_list# update min node if neededif h2.min_node.key < H.min_node.key:H.min_node = h2.min_node# update total nodesH.total_nodes = self.total_nodes + h2.total_nodesreturn H# if a child node becomes smaller than its parent node we# cut this child node off and bring it up to the root listdef cut(self, x, y):self.remove_from_child_list(y, x)y.degree -= 1self.merge_with_root_list(x)x.parent = Nonex.mark = False# cascading cut of parent node to obtain good time boundsdef cascading_cut(self, y):z = y.parentif z is not None:if y.mark is False:y.mark = Trueelse:self.cut(y, z)self.cascading_cut(z)# combine root nodes of equal degree to consolidate the heap# by creating a list of unordered binomial treesdef consolidate(self):A = [None] * int(math.log(self.total_nodes) * 2)nodes = [w for w in self.iterate(self.root_list)]for w in range(0, len(nodes)):x = nodes[w]d = x.degreewhile A[d] != None:y = A[d]if x.key > y.key:temp = xx, y = y, tempself.heap_link(y, x)A[d] = Noned += 1A[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 loopfor i in range(0, len(A)):if A[i] is not None:if A[i].key < self.min_node.key:self.min_node = A[i]# actual linking of one node to another in the root list# while also updating the child linked listdef heap_link(self, y, x):self.remove_from_root_list(y)y.left = y.right = yself.merge_with_child_list(x, y)x.degree += 1y.parent = xy.mark = False# merge a node with the doubly linked root listdef merge_with_root_list(self, node):if self.root_list is None:self.root_list = nodeelse:node.right = self.root_list.rightnode.left = self.root_listself.root_list.right.left = nodeself.root_list.right = node# merge a node with the doubly linked child list of a root nodedef merge_with_child_list(self, parent, node):if parent.child is None:parent.child = nodeelse:node.right = parent.child.rightnode.left = parent.childparent.child.right.left = nodeparent.child.right = node# remove a node from the doubly linked root listdef remove_from_root_list(self, node):if node == self.root_list:self.root_list = node.rightnode.left.right = node.rightnode.right.left = node.left# remove a node from the doubly linked child listdef remove_from_child_list(self, parent, node):if parent.child == parent.child.right:parent.child = Noneelif parent.child == node:parent.child = node.rightnode.right.parent = parentnode.left.right = node.rightnode.right.left = node.leftdef fibonacci_heap_sort(arr):heap = FibonacciHeap()for key in arr:heap.insert(key)sorted_arr = []while heap.total_nodes > 0:sorted_arr.append(heap.extract_min().key)return sorted_arr
C++模板代码实现
template <class V>
class FibonacciHeap;template <class V>
struct node
{
private:node<V> *prev;node<V> *next;node<V> *child;node<V> *parent;V value;int degree;bool marked;public:friend class FibonacciHeap<V>;node<V> *getPrev() { return prev; }node<V> *getNext() { return next; }node<V> *getChild() { return child; }node<V> *getParent() { return parent; }V getValue() { return value; }bool isMarked() { return marked; }bool hasChildren() { return child; }bool hasParent() { return parent; }
};template <class V>
class FibonacciHeap
{
protected:node<V> *heap;public:FibonacciHeap(){heap = _empty();}virtual ~FibonacciHeap(){if (heap){_deleteAll(heap);}}node<V> *insert(V value){node<V> *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<V> *old = heap;heap = _removeMinimum(heap);V ret = old->value;delete old;return ret;}void decreaseKey(node<V> *n, V value){heap = _decreaseKey(heap, n, value);}node<V> *find(V value){return _find(heap, value);}private:node<V> *_empty(){return nullptr;}node<V> *_singleton(V value){node<V> *n = new node<V>;n->value = value;n->prev = n->next = n;n->degree = 0;n->marked = false;n->child = nullptr;n->parent = nullptr;return n;}node<V> *_merge(node<V> *a, node<V> *b){if (a == nullptr)return b;if (b == nullptr)return a;if (a->value > b->value){node<V> *temp = a;a = b;b = temp;}node<V> *an = a->next;node<V> *bp = b->prev;a->next = b;b->prev = a;an->prev = bp;bp->next = an;return a;}void _deleteAll(node<V> *n){if (n != nullptr){node<V> *c = n;do{node<V> *d = c;c = c->next;_deleteAll(d->child);delete d;} while (c != n);}}void _addChild(node<V> *parent, node<V> *child){child->prev = child->next = child;child->parent = parent;parent->degree++;parent->child = _merge(parent->child, child);}void _unMarkAndUnParentAll(node<V> *n){if (n == nullptr)return;node<V> *c = n;do{c->marked = false;c->parent = nullptr;c = c->next;} while (c != n);}node<V> *_removeMinimum(node<V> *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<V> *trees[64] = {nullptr};while (true){if (trees[n->degree] != nullptr){node<V> *t = trees[n->degree];if (t == n)break;trees[n->degree] = nullptr;if (n->value < t->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<V> *min = n;node<V> *start = n;do{if (n->value < min->value)min = n;n = n->next;} while (n != start);return min;}node<V> *_cut(node<V> *heap, node<V> *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<V> *_decreaseKey(node<V> *heap, node<V> *n, V value){if (n->value < value)return heap;n->value = value;if (n->parent){if (n->value < n->parent->value){heap = _cut(heap, n);node<V> *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 < heap->value){heap = n;}}return heap;}node<V> *_find(node<V> *heap, V value){node<V> *n = heap;if (n == nullptr)return nullptr;do{if (n->value == value)return n;node<V> *ret = _find(n->child, value);if (ret)return ret;n = n->next;} while (n != heap);return nullptr;}
};template <class T>
void FibonacciHeapSort(vector<T> &data)
{FibonacciHeap<T> heap;auto dataSize = data.size();for (auto i = 0; i < dataSize; i++)heap.insert(data[i]);for (auto i = 0; i < dataSize; i++)data[i] = heap.removeMinimum();
}

二叉堆排序

二叉堆排序是一种基于比较的排序算法,它利用二叉堆这种数据结构来进行排序。二叉堆是一种特殊的堆,它是一个近似完全二叉树,满足任一非叶子节点的值不大于或不小于其左右孩子节点的值。根据堆的这一特性,二叉堆分为最大堆和最小堆。在最大堆中,每个父节点的值都大于或等于其孩子节点的值;在最小堆中,每个父节点的值都小于或等于其孩子节点的值。

基本概念
  1. 二叉堆的性质:对于最大堆,每个父节点的值都大于或等于其孩子节点的值;对于最小堆,每个父节点的值都小于或等于其孩子节点的值。
  2. 堆的表示:通常使用数组来表示堆,对于任意节点i(假设数组从1开始索引),其左孩子为2i,右孩子为2i+1,父节点为i/2(向下取整)。
算法步骤
  1. 构建堆:将无序数组构造成一个最大堆(或最小堆)。
  2. 调整堆:将堆顶元素(最大或最小值)与数组末尾元素交换,然后调整堆,使其满足堆的性质。
  3. 重复调整:重复步骤2,直到堆中只剩下一个元素,此时数组已排序。
伪代码
二叉堆排序(array):构建最大堆(array)for i = length(array) downto 2:交换array[1]和array[i]调整堆(array, 1, i - 1)end for
end 二叉堆排序
构建最大堆(array):n = length(array)for i = n/2 downto 1:调整堆(array, i, n)end for
end 构建最大堆
调整堆(array, i, n):while 2*i <= n:j = 2*iif j + 1 <= n and array[j] < array[j + 1]:j = j + 1if array[i] < array[j]:交换array[i]和array[j]i = jelse:breakend while
end 调整堆
Python代码实现
class MaxHeap:def __init__(self):self.heap = []def parent(self, i):return (i - 1) // 2def left_child(self, i):return 2 * i + 1def right_child(self, i):return 2 * i + 2def has_left_child(self, i):return self.left_child(i) < len(self.heap)def has_right_child(self, i):return self.right_child(i) < len(self.heap)def swap(self, i, j):self.heap[i], self.heap[j] = self.heap[j], self.heap[i]def heapify_up(self, i):while i > 0 and self.heap[self.parent(i)] < self.heap[i]:self.swap(i, self.parent(i))i = self.parent(i)def heapify_down(self, i):largest = iif self.has_left_child(i) and self.heap[self.left_child(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 Nonemax_value = self.heap[0]self.heap[0] = self.heap[-1]self.heap.pop()self.heapify_down(0)return max_valuedef 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) == 0def get_max(self):if self.is_empty():return Nonereturn 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 <iostream>
#include <vector>
#include <algorithm>template <typename T>
void maxHeapify(std::vector<T>& arr, int i, int n) {int left = 2 * i + 1;int right = 2 * i + 2;int largest = i;if (left < n && arr[left] > arr[largest]) {largest = left;}if (right < n && arr[right] > arr[largest]) {largest = right;}if (largest != i) {std::swap(arr[i], arr[largest]);maxHeapify(arr, largest, n);}
}template <typename T>
void heapSort(std::vector<T>& arr) {int n = arr.size();// Build max heapfor (int i = n / 2 - 1; i >= 0; i--) {maxHeapify(arr, i, n);}// Extract elements from heapfor (int i = n - 1; i >= 0; i--) {std::swap(arr[0], arr[i]);maxHeapify(arr, 0, i);}
}

这段代码首先定义了一个maxHeapify函数,用于调整堆,使其满足最大堆的性质。然后定义了heapSort函数,该函数首先构建一个最大堆,然后通过不断将堆顶元素与数组末尾元素交换并调整堆,实现了排序。最后在main函数中测试了排序算法。

二叉堆实现
template <typename T>
class BinaryHeap
{
private:vector<T> heap;// 用于将新插入的元素上浮到正确位置void siftUp(int index){while (index > 0 && heap[(index - 1) / 2] < heap[index]){swap(heap[index], heap[(index - 1) / 2]);index = (index - 1) / 2;}}// 用于将堆顶元素下沉到正确位置void siftDown(int index){int left = 2 * index + 1;int right = 2 * index + 2;int largest = index;if (left < heap.size() && heap[left] > heap[largest]){largest = left;}if (right < heap.size() && heap[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 << elem << " ";}cout << endl;}
};template <class T>
void BinaryHeapSort(vector<T> &data)
{BinaryHeap<T> heap;auto dataSize = data.size();for (auto i = 0; i < dataSize; i++)heap.insert(data[i]);for (auto i = 0; i < dataSize; i++)data[i] = heap.pop();
}

完整的项目代码

Python 代码

import mathclass Person:def __init__(self, name, age, score):self.name = nameself.age = ageself.score = scoredef __lt__(self, other):return self.score < other.scoredef __le__(self, other):return self.score <= other.scoredef __eq__(self, other):return self.score == other.score and self.age == other.age and self.name == other.namedef __ne__(self, other):return not self.__eq__(other)def __gt__(self, other):return self.score > other.scoredef __ge__(self, other):return self.score >= other.scoredef get_name(self):return self.namedef get_age(self):return self.agedef get_score(self):return self.scoredef heapify(arr, n, i):largest = ileft = 2 * i + 1right = 2 * i + 2if left < n and arr[i] < arr[left]:largest = leftif right < n and arr[largest] < arr[right]:largest = rightif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heapsort(arr):n = len(arr)for i in range(n//2 - 1, -1, -1):heapify(arr, n, i)for i in range(n-1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)def test_heap_sort():data = [9, 8, 3, 7, 5, 6, 4, 1]heapsort(data)print(data)d_data = [9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1]heapsort(d_data)print(d_data)c_data = ['a', 'c', 'b', 'd', 'e']heapsort(c_data)print(c_data)p_data = [Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)]heapsort(p_data)for person in p_data:print(person.get_name(), person.get_age(), person.get_score())class MaxHeap:def __init__(self):self.heap = []def parent(self, i):return (i - 1) // 2def left_child(self, i):return 2 * i + 1def right_child(self, i):return 2 * i + 2def has_left_child(self, i):return self.left_child(i) < len(self.heap)def has_right_child(self, i):return self.right_child(i) < len(self.heap)def swap(self, i, j):self.heap[i], self.heap[j] = self.heap[j], self.heap[i]def heapify_up(self, i):while i > 0 and self.heap[self.parent(i)] < self.heap[i]:self.swap(i, self.parent(i))i = self.parent(i)def heapify_down(self, i):largest = iif self.has_left_child(i) and self.heap[self.left_child(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 Nonemax_value = self.heap[0]self.heap[0] = self.heap[-1]self.heap.pop()self.heapify_down(0)return max_valuedef 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) == 0def get_max(self):if self.is_empty():return Nonereturn 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 classclass Node:def __init__(self, key, value):self.key = keyself.value = valueself.parent = self.child = self.left = self.right = Noneself.degree = 0self.mark = False# function to iterate through a doubly linked listdef iterate(self, head):node = stop = headflag = Falsewhile True:if node == stop and flag is True:breakelif node == stop:flag = Trueyield nodenode = node.right# pointer to the head and minimum node in the root listroot_list, min_node = None, None# maintain total node count in full fibonacci heaptotal_nodes = 0# return min node in O(1) timedef 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_nodeif z is not None:if z.child is not None:# attach child nodes to root listchildren = [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 = Noneself.remove_from_root_list(z)# set new min node in heapif z == z.right:self.min_node = self.root_list = Noneelse:self.min_node = z.rightself.consolidate()self.total_nodes -= 1return 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 laterdef insert(self, key, value=None):n = self.Node(key, value)n.left = n.right = nself.merge_with_root_list(n)if self.min_node is None or n.key < self.min_node.key:self.min_node = nself.total_nodes += 1return n# modify the key of some node in the heap in O(1) timedef decrease_key(self, x, k):if k > x.key:return Nonex.key = ky = x.parentif y is not None and x.key < y.key:self.cut(x, y)self.cascading_cut(y)if x.key < self.min_node.key:self.min_node = x# merge two fibonacci heaps in O(1) time by concatenating the root lists# the root of the new root list becomes equal to the first list and the second# list is simply appended to the end (then the proper min node is determined)def merge(self, h2):H = FibonacciHeap()H.root_list, H.min_node = self.root_list, self.min_node# fix pointers when merging the two heapslast = h2.root_list.lefth2.root_list.left = H.root_list.leftH.root_list.left.right = h2.root_listH.root_list.left = lastH.root_list.left.right = H.root_list# update min node if neededif h2.min_node.key < H.min_node.key:H.min_node = h2.min_node# update total nodesH.total_nodes = self.total_nodes + h2.total_nodesreturn H# if a child node becomes smaller than its parent node we# cut this child node off and bring it up to the root listdef cut(self, x, y):self.remove_from_child_list(y, x)y.degree -= 1self.merge_with_root_list(x)x.parent = Nonex.mark = False# cascading cut of parent node to obtain good time boundsdef cascading_cut(self, y):z = y.parentif z is not None:if y.mark is False:y.mark = Trueelse:self.cut(y, z)self.cascading_cut(z)# combine root nodes of equal degree to consolidate the heap# by creating a list of unordered binomial treesdef consolidate(self):A = [None] * int(math.log(self.total_nodes) * 2)nodes = [w for w in self.iterate(self.root_list)]for w in range(0, len(nodes)):x = nodes[w]d = x.degreewhile A[d] != None:y = A[d]if x.key > y.key:temp = xx, y = y, tempself.heap_link(y, x)A[d] = Noned += 1A[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 loopfor i in range(0, len(A)):if A[i] is not None:if A[i].key < self.min_node.key:self.min_node = A[i]# actual linking of one node to another in the root list# while also updating the child linked listdef heap_link(self, y, x):self.remove_from_root_list(y)y.left = y.right = yself.merge_with_child_list(x, y)x.degree += 1y.parent = xy.mark = False# merge a node with the doubly linked root listdef merge_with_root_list(self, node):if self.root_list is None:self.root_list = nodeelse:node.right = self.root_list.rightnode.left = self.root_listself.root_list.right.left = nodeself.root_list.right = node# merge a node with the doubly linked child list of a root nodedef merge_with_child_list(self, parent, node):if parent.child is None:parent.child = nodeelse:node.right = parent.child.rightnode.left = parent.childparent.child.right.left = nodeparent.child.right = node# remove a node from the doubly linked root listdef remove_from_root_list(self, node):if node == self.root_list:self.root_list = node.rightnode.left.right = node.rightnode.right.left = node.left# remove a node from the doubly linked child listdef remove_from_child_list(self, parent, node):if parent.child == parent.child.right:parent.child = Noneelif parent.child == node:parent.child = node.rightnode.right.parent = parentnode.left.right = node.rightnode.right.left = node.leftdef fibonacci_heap_sort(arr):heap = FibonacciHeap()for key in arr:heap.insert(key)sorted_arr = []while heap.total_nodes > 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 <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <list>
#include <iterator>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 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 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!= 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<= for other fnction 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>= 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;}// 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 <typename RandomAccessIterator>
void siftDown(RandomAccessIterator start, RandomAccessIterator end, RandomAccessIterator root)
{auto child = root;advance(child, distance(start, root) + 1);if (child < end){auto sibling = child;++sibling;if (sibling<end && * sibling> * child){child = sibling;}if (*child > *root){iter_swap(root, child);siftDown(start, end, child);}}
}template <typename RandomAccessIterator>
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 <typename RandomAccessIterator>
void heapSort(RandomAccessIterator start, RandomAccessIterator end)
{makeHeap<RandomAccessIterator>(start, end);while (start != end){--end;iter_swap(start, end);siftDown(start, end, start);}
}void heapSortTestCase()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};heapSort<vector<int>::iterator>(data.begin(), data.end());for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};heapSort<vector<double>::iterator>(dData.begin(), dData.end());for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};heapSort<vector<char>::iterator>(cData.begin(), cData.end());for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};heapSort<vector<Person>::iterator>(pData.begin(), pData.end());for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}template <typename T>
void maxHeapify(vector<T> &arr, int i, int n)
{int left = 2 * i + 1;int right = 2 * i + 2;int largest = i;if (left < n && arr[left] > arr[largest]){largest = left;}if (right < n && arr[right] > arr[largest]){largest = right;}if (largest != i){swap(arr[i], arr[largest]);maxHeapify(arr, largest, n);}
}template <typename T>
void binaryHeapSort(vector<T> &arr)
{int n = arr.size();// Build max heapfor (int i = n / 2 - 1; i >= 0; i--){maxHeapify(arr, i, n);}// Extract elements from heapfor (int i = n - 1; i >= 0; i--){swap(arr[0], arr[i]);maxHeapify(arr, 0, i);}
}void binaryHeapSortTestCase()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};binaryHeapSort<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};binaryHeapSort<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};binaryHeapSort<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};binaryHeapSort<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}template <typename T>
class BinaryHeap
{
private:vector<T> heap;// 用于将新插入的元素上浮到正确位置void siftUp(int index){while (index > 0 && heap[(index - 1) / 2] < heap[index]){swap(heap[index], heap[(index - 1) / 2]);index = (index - 1) / 2;}}// 用于将堆顶元素下沉到正确位置void siftDown(int index){int left = 2 * index + 1;int right = 2 * index + 2;int largest = index;if (left < heap.size() && heap[left] > heap[largest]){largest = left;}if (right < heap.size() && heap[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 << elem << " ";}cout << endl;}
};template <class T>
void BinaryHeapSort(vector<T> &data)
{BinaryHeap<T> heap;auto dataSize = data.size();for (auto i = 0; i < dataSize; i++)heap.insert(data[i]);for (auto i = 0; i < dataSize; i++)data[i] = heap.pop();
}void BinaryHeapUnitTest()
{BinaryHeap<int> maxHeap;maxHeap.insert(10);maxHeap.insert(20);maxHeap.insert(15);maxHeap.insert(17);maxHeap.insert(25);maxHeap.print();                            // 应该输出 25 20 15 17 10cout << "Peek: " << maxHeap.peek() << endl; // 应该输出 25maxHeap.remove();maxHeap.print(); // 应该输出 20 17 15 10
}void BinaryHeapSortTestCase()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};BinaryHeapSort<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};BinaryHeapSort<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};BinaryHeapSort<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};BinaryHeapSort<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}template <class V>
class FibonacciHeap;template <class V>
struct node
{
private:node<V> *prev;node<V> *next;node<V> *child;node<V> *parent;V value;int degree;bool marked;public:friend class FibonacciHeap<V>;node<V> *getPrev() { return prev; }node<V> *getNext() { return next; }node<V> *getChild() { return child; }node<V> *getParent() { return parent; }V getValue() { return value; }bool isMarked() { return marked; }bool hasChildren() { return child; }bool hasParent() { return parent; }
};template <class V>
class FibonacciHeap
{
protected:node<V> *heap;public:FibonacciHeap(){heap = _empty();}virtual ~FibonacciHeap(){if (heap){_deleteAll(heap);}}node<V> *insert(V value){node<V> *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<V> *old = heap;heap = _removeMinimum(heap);V ret = old->value;delete old;return ret;}void decreaseKey(node<V> *n, V value){heap = _decreaseKey(heap, n, value);}node<V> *find(V value){return _find(heap, value);}private:node<V> *_empty(){return nullptr;}node<V> *_singleton(V value){node<V> *n = new node<V>;n->value = value;n->prev = n->next = n;n->degree = 0;n->marked = false;n->child = nullptr;n->parent = nullptr;return n;}node<V> *_merge(node<V> *a, node<V> *b){if (a == nullptr)return b;if (b == nullptr)return a;if (a->value > b->value){node<V> *temp = a;a = b;b = temp;}node<V> *an = a->next;node<V> *bp = b->prev;a->next = b;b->prev = a;an->prev = bp;bp->next = an;return a;}void _deleteAll(node<V> *n){if (n != nullptr){node<V> *c = n;do{node<V> *d = c;c = c->next;_deleteAll(d->child);delete d;} while (c != n);}}void _addChild(node<V> *parent, node<V> *child){child->prev = child->next = child;child->parent = parent;parent->degree++;parent->child = _merge(parent->child, child);}void _unMarkAndUnParentAll(node<V> *n){if (n == nullptr)return;node<V> *c = n;do{c->marked = false;c->parent = nullptr;c = c->next;} while (c != n);}node<V> *_removeMinimum(node<V> *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<V> *trees[64] = {nullptr};while (true){if (trees[n->degree] != nullptr){node<V> *t = trees[n->degree];if (t == n)break;trees[n->degree] = nullptr;if (n->value < t->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<V> *min = n;node<V> *start = n;do{if (n->value < min->value)min = n;n = n->next;} while (n != start);return min;}node<V> *_cut(node<V> *heap, node<V> *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<V> *_decreaseKey(node<V> *heap, node<V> *n, V value){if (n->value < value)return heap;n->value = value;if (n->parent){if (n->value < n->parent->value){heap = _cut(heap, n);node<V> *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 < heap->value){heap = n;}}return heap;}node<V> *_find(node<V> *heap, V value){node<V> *n = heap;if (n == nullptr)return nullptr;do{if (n->value == value)return n;node<V> *ret = _find(n->child, value);if (ret)return ret;n = n->next;} while (n != heap);return nullptr;}
};class DotFibonacciHeap : public FibonacciHeap<int>
{
public:void dump(){printf("digraph G {\n");if (heap == nullptr){printf("empty;\n}\n");return;}printf("minimum -> \"%p\" [constraint=false];\n", heap);node<int> *c = heap;do{_dumpChildren(c);c = c->getNext();} while (c != heap);printf("}\n");}private:void _dumpChildren(node<int> *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<int> *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<int> *nine = h.insert(90);h.removeMinimum();h.removeMinimum();h.removeMinimum();for (int i = 0; i < 20; i += 2)h.insert(30 - i);for (int i = 0; i < 4; i++)h.removeMinimum();for (int i = 0; i < 20; i += 2)h.insert(30 - i);h.insert(23);for (int i = 0; i < 7; i++)h.removeMinimum();h.decreaseKey(nine, 1);h.decreaseKey(h.find(28), 2);h.decreaseKey(h.find(23), 3);h.dump();
}template <class T>
void FibonacciHeapSort(vector<T> &data)
{FibonacciHeap<T> heap;auto dataSize = data.size();for (auto i = 0; i < dataSize; i++)heap.insert(data[i]);for (auto i = 0; i < dataSize; i++)data[i] = heap.removeMinimum();
}void FibonacciHeapSortTestCase()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};FibonacciHeapSort<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};FibonacciHeapSort<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};FibonacciHeapSort<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};FibonacciHeapSort<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}int main()
{cout << "Heap Sort Case:" << endl;heapSortTestCase();cout << "Binary Heap Sort Case Without DataStructure:" << endl;binaryHeapSortTestCase();cout << "Binary Heap Sort Case With DataStructure:" << endl;BinaryHeapUnitTest();BinaryHeapSortTestCase();cout << "Fibonacci Heap Sort Case:" << endl;DotFibonacciHeapUnitTest();FibonacciHeapSortTestCase();return 0;
}

个人格言

追寻与内心共鸣的生活,未来会逐渐揭晓答案。

Pursue the life that resonates with your heart, and the future will gradually reveal the answer.

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2812318.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

goland配置新增文件头

参考&#xff1a; goland函数注释生成插件 goland函数注释生成插件_goland自动加函数说明-CSDN博客 GoLand 快速添加方法注释 GoLand 快速添加方法注释_goland批量注释-CSDN博客 goland 如何设置头注释&#xff0c;自定义author和data goland 如何设置头注释&#xff0c;自定…

【踩坑】修复xrdp无法关闭Authentication Required验证窗口

转载请注明出处&#xff1a;小锋学长生活大爆炸[xfxuezhang.cn] 问题如下&#xff0c;时不时出现&#xff0c;有时还怎么都关不掉&#xff0c;很烦&#xff1a; 解决方法一&#xff1a;命令行输入 dbus-send --typemethod_call --destorg.gnome.Shell /org/gnome/Shell org.gn…

【web APIs】1、(学习笔记)有案例!

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、概念二、使用步骤1.获取DOM对象2.操作元素内容3.属性修改3.1.常用属性修改3.2.控制样式属性3.3.操作类名(className) 操作CSS3.4.操作表单元素属性3.5.自定…

Mycat核心教程--ZooKeeper集群搭建【三】

Mycat核心教程--ZooKeeper集群搭建 八、 ZooKeeper集群搭建8.1.ZooKeeper简介8.2.数据复制的好处8.3.Zookeeper设计目的8.4.zookeeper集群包括3种角色8.4.1.Leader角色8.4.2.Follower 角色8.4.3.Observer 角色 8.5.zookeeper集群工作流程8.6.zookeeper集群节点数量为奇数&#…

如何选择适合的工具,将由图片合成的PDF转为Excel?

在数字化时代&#xff0c;PDF文件已经成为我们日常工作中不可或缺的一部分。然而&#xff0c;有时候我们需要将这些PDF文件中的图片转换成Excel格式&#xff0c;以便进行进一步的数据分析和处理。这时&#xff0c;选择一款适合的由图片组成的PDF转Excel工具就显得尤为重要。本文…

mysql order by布尔盲注

什么是order by 在MySQL支持使用ORDER BY语句对查询结果集进行排序处理&#xff0c;使用ORDER BY语句不仅支持对单列数据的排序&#xff0c;还支持对数据表中多列数据的排序。语法格式如下 select * from 表名 order by 列名(或者数字) asc&#xff1b;升序(默认升序) selec…

东莞IBM服务器维修之IBM x3630 M4阵列恢复

记录东莞某抖音电商公司送修一台IBM SYSTEM X3630 M4文档服务器RAID6故障导致数据丢失的恢复案例 时间&#xff1a;2024年02月20日&#xff0c; 服务器品牌&#xff1a;IBM System x3630 M4&#xff0c;阵列卡用的是DELL PERC H730P 服务器用途和用户位置&#xff1a;某抖音电…

深度学习目标检测】二十、基于深度学习的雾天行人车辆检测系统-含数据集、GUI和源码(python,yolov8)

雾天车辆行人检测在多种场景中扮演着至关重要的角色。以下是其作用的几个主要方面&#xff1a; 安全性提升&#xff1a;雾天能见度低&#xff0c;视线受阻&#xff0c;这使得驾驶者和行人在道路上的感知能力大大降低。通过车辆行人检测技术&#xff0c;可以在雾天条件下及时发现…

GEE数据集——全球 30 米不透水表面动态数据集 (GISD30)

全球 30 米不透水表面动态数据集 (GISD30) 全球 30 米不透水表面动态数据集 (GISD30) 为了解 1985 年至 2020 年全球不断变化的不透水表面景观提供了宝贵的资源。该数据集在城市可持续发展、人为碳排放评估和全球生态环境建模等领域具有深远的科学意义和实际应用价值。GISD30 是…

高数考研 -- 公式总结(更新中)

1. 两个重要极限 (1) lim ⁡ x → 0 sin ⁡ x x 1 \lim _{x \rightarrow 0} \frac{\sin x}{x}1 limx→0​xsinx​1, 推广形式 lim ⁡ f ( x ) → 0 sin ⁡ f ( x ) f ( x ) 1 \lim _{f(x) \rightarrow 0} \frac{\sin f(x)}{f(x)}1 limf(x)→0​f(x)sinf(x)​1. (2) lim ⁡…

ABAP 发送带EXCEL邮件

前言 没啥特殊需求&#xff0c;就是有个库龄报表用户想整邮件发送 实现 用的最简单的XLS文件作为excel附件发送出去 观察XLS文件的纯文本格式&#xff0c;每列之间用TAB制表符分隔&#xff0c;每行之间用回车符分隔 思路也比较明确&#xff0c;在SAP中实现这种格式&#xf…

命名元组(python)

命名元组与元组的差异&#xff0c;命名元组和字典&#xff0c;哪个效率更高。 (笔记模板由python脚本于2024年02月26日 12:31:36创建&#xff0c;本篇笔记适合熟悉python元组和字典的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ F…

面试redis篇-13Redis为什么那么快

Redis是纯内存操作,执行速度非常快采用单线程,避免不必要的上下文切换可竞争条件,多线程还要考虑线程安全问题使用I/O多路复用模型,非阻塞IOI/O多路复用模型 Redis是纯内存操作,执行速度非常快,它的性能瓶颈是网络延迟而不是执行速度, I/O多路复用模型主要就是实现了高效…

Lua速成(2)

一、流程控制 Lua 编程语言流程控制语句通过程序设定一个或多个条件语句来设定。在条件为 true 时执行指定程序代码&#xff0c;在条件为 false 时执行其他指定代码。 控制结构的条件表达式结果可以是任何值&#xff0c;Lua认为false和nil为假&#xff0c;true和非nil为真。 …

C++ list详解以及模拟实现

目录 1.list的使用 1.1list的定义 1.2list的使用 1.3list iterator使用 1.4list capacity 1.5list element access 1.6list增删查改 2.list迭代器失效问题 3.list的模拟实现 1.list的使用 1.1list的定义 1. list是可以在常数范围内在任意位置进行插入和删除的序列式容…

探索便捷办公新选择:ONLYOFFICE 桌面编辑器

目录 引言 1. ONLYOFFICE 桌面编辑器简介 2. 功能特点 2.1 多格式支持 2.2 实时协作编辑 2.3 兼容性与格式保持 2.4 丰富的编辑功能 3. 使用方法 3.1 下载安装 3.2 打开文档 3.3 编辑文档 3.4 保存和共享 4. 注意事项 4.1 版本更新 4.2 网络连接 4.3 安全性 5.…

matlab 方向向量约束的PCA快速粗配准

目录 一、算法原理二、代码实现三、结果展示本文由CSDN点云侠原创,原文链接。如果你不是在点云侠的博客中看到该文章,那么此处便是不要脸的GPT爬虫。 一、算法原理 该方法由本人原创,目前尚未见有相关论文用到。具体原理看代码即可。 二、代码实现 clc;clear; %% ------…

rtthread stm32h743的使用(一)新工程建立

我们要在rtthread studio 开发环境中建立stm32h743xih6芯片的工程。我们使用一块stm32h743及fpga的核心板完成相关实验&#xff0c;核心板如图&#xff1a; 1.打开rtthread studio填写芯片型号及调试口&#xff0c;我们的调试串口为USART1_PA9,PA10。 2.编译新工程并且下载 …

C++:类与对象(2)

创作不易&#xff0c;感谢三连&#xff01; 一、六大默认成员函数 C为了弥补C语言的不足&#xff0c;设置了6个默认成员函数 二、构造函数 2.1 概念 在我们学习数据结构的时候&#xff0c;我们总是要在使用一个对象前进行初始化&#xff0c;这似乎已经成为了一件无法改变的…