讨论/《排序算法全解析》 - 堆排序/
《排序算法全解析》 - 堆排序
共 10 个回复

这例子,味道太浓了。。。

5

按照臭的程度应该是小顶堆吧

2

修饰器方法,请发一下呗,万分感谢~

总结一下:
利用大顶堆的特性:根节点的值大于等于左右子节点。当数组呈大顶堆排列时,交换堆顶节点和最大索引节点,将堆顶数字置换到数组尾部,这个数一定是最大的。再次调整剩余堆(除去最后一个数字),使堆顶三角(堆顶三角一定包含堆中最大的数)中最大数位于根节点,找到剩余堆中最大索引节点,并与根节点交换……这样,不断找出最大数,并与最大索引数字交换将最大数放置于数组末尾,并且缩小堆范围,选出堆顶三角中的最大数与末尾数字交换位置,最后实现数组的升序排列。

仔细一点可以看出,最大数与堆中最大索引对应数字交换,跨越了中间多个数字,可以免除相邻数字间不必要的比较(因为大顶堆在宏观上是从大到小排序的),和希尔排序章节中提到的思想一致。

按香的程度,香啊香

生活中或许会有这样的黑幕,但程序不会欺骗我们。

代码中的maxHeapify中的递归没有写结束条件,应该在开头添加
if((i<<1)+1>len)
return;

贴个python实现,供参考

class Heap:
    @staticmethod
    def heapSort(nums, reverse=False):
        Heap.heapify(nums, not reverse)
        for i in range(len(nums) - 1, -1, -1):
            nums[i], nums[0] = nums[0], nums[i]
            if reverse:
                Heap.minHeap(nums, 0, i)
            else:
                Heap.maxHeap(nums, 0, i)
        
    @staticmethod
    def heapify(nums, maxHeap=True):
        for i in range(len(nums) // 2 - 1, -1, -1):
            if maxHeap:
                Heap.maxHeap(nums, i, len(nums))
            else:
                Heap.minHeap(nums, i, len(nums))

    @staticmethod
    def maxHeap(nums, i, heap_size):
        left = 2 * i + 1
        right = left + 1
        max_id = i
        if left < heap_size and nums[left] > nums[max_id]:
            max_id = left
        if right < heap_size and nums[right] > nums[max_id]:
            max_id = right
        if max_id != i:
            nums[i], nums[max_id] = nums[max_id], nums[i]
            Heap.maxHeap(nums, max_id, heap_size)
    
    @staticmethod
    def minHeap(nums, i, heap_size):
        left = 2 * i + 1
        right = left + 1
        min_id = i
        if left < heap_size and nums[left] < nums[min_id]:
            min_id = left
        if right < heap_size and nums[right] < nums[min_id]:
            min_id = right
        if min_id != i:
            nums[i], nums[min_id] = nums[min_id], nums[i]
            Heap.minHeap(nums, min_id, heap_size)

有些书上用的是“维护”的概念会比较容易引起思考,这里把最大值换到最后再进行的maxHeapify其实就是一次维护。
至于维护后为什么仍然可以满足:构成最大堆->产出最大值->...->构成最大堆->产出最大值
就要考虑两个命题了:
①把最大值换成一个无名小辈后,无名小辈sinking的过程结束后,整体仍然是最大堆
②最大堆的最大值一定在头三个元素内(这不是句废话,这说明第二层可以产出最大值)

年前还到处找排序的题做,现在就有词卡了,Leetcode比我效率高