Heap sort
| EN | CN |
Heap intro
Heaps are usually implemented with an implicit heap data structure, which is an implicit data structure consisting of an array (fixed size or dynamic array) where each element represents a tree node whose parent/children relationship is defined implicitly by their index. After an element is inserted into or deleted from a heap, the heap property may be violated and the heap must be balanced by swapping elements within the array.
the children of the node at position n would be at positions 2n and 2n + 1 in a one-based array, or 2n + 1 and 2n + 2 in a zero-based array.
Complexity
| Average time complexity | (n log n) |
| Worst time complexity | O (n log n) |
| Optimal time complexity | O (n log n) |
| Space Complexity | O (n) total, O (1) auxiliary |
| Best solution | No |
Steps
Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in O(n) operations. Swap the first element of the list with the final element. Decrease the considered range of the list by one. Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap. Go to step (2) unless the considered range of the list is one element.
Source code
堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列； 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
堆的定义
n个结点的堆，高度为 logn。根为第0层，则第i层结点个数为2^i，考虑一个元素在堆中向下移动的距离，这种算法时间代价为Ο（n) 由于堆有层深，插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是O(logn)。
复杂度
| 平均时间复杂度 | (n\log n) |
| 最坏时间复杂度 | O(n\log n) |
| 最优时间复杂度 | O(n\log n) |
| 空间复杂度 | O(n) total, O(1) auxiliary |
| 最佳解 | 不是 |
算法步骤
-
创建一个堆 H[0……n-1]；
-
把堆首（最大值）和堆尾互换；
-
把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
-
重复步骤 2，直到堆的尺寸为 1。