堆排序利用了二叉堆的特性来做,二叉堆通常用数组表示,并且二叉堆是一颗完全二叉树(所有叶节点(最底层的节点)都是从左往右顺序排序,并且其他层的节点都是满的)。二叉堆又分为大根堆与小根堆。
堆排序的原理就是组成一个大根堆或者小根堆。以小根堆为例,某个节点的左边子节点索引是 i * 2 + 1
,右边是 i * 2 + 2
,父节点是 (i - 1) /2
。
以下是实现该算法的代码
function heap(array) { checkArray(array) // 将最大值交换到首位 for (let i = 0; i < array.length; i++) { heapInsert(array, i) } let size = array.length // 交换首位和末尾 swap(array, 0, --size) while (size > 0) { heapify(array, 0, size) swap(array, 0, --size) } return array } function heapInsert(array, index) { // 如果当前节点比父节点大,就交换 while (array[index] > array[parseInt((index - 1) / 2)]) { swap(array, index, parseInt((index - 1) / 2)) // 将索引变成父节点 index = parseInt((index - 1) / 2) } } function heapify(array, index, size) { let left = index * 2 + 1 while (left < size) { // 判断左右节点大小 let largest = left + 1 < size && array[left] < array[left + 1] ? left + 1 : left // 判断子节点和父节点大小 largest = array[index] < array[largest] ? largest : index if (largest === index) break swap(array, index, largest) index = largest left = index * 2 + 1 } }
以上代码实现了小根堆,如果需要实现大根堆,只需要把节点对比反一下就好。
该算法的复杂度是 O(logN)
本文作者:毛超颖
本文链接:
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!