为什么可以用完全二叉堆实现堆排序

热心网友 · 2018-4-30 01:12:42

堆排序是一种选择排序。是不稳定的排序方法。时间复杂度为O(nlog2n)。特点是在排序过程中，将排序数组看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大(或最小)的记录。
其基本思想是
1、将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2、将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
3、重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。

P.S.
大根堆和小根堆
堆：是一颗完全二叉树。
大根堆：所有节点的子节点比其自身小的堆
小根堆：所有节点的子节点比其自身大的堆

为什么可以用完全二叉堆实现堆排序

1 个回复