402v

最近在刷LeetCode，顺便把之前不会、掌握的不熟练的算法都看一遍，今天要说的是堆排序。

###堆排序堆排序是利用堆（大顶堆或小顶堆都可）的性质，每次从堆顶取一个元素，然后对堆重新调整，最后完成排序的排序算法，时间复杂度和快速排序、归并排序一样都是O(n*log n)。并且堆的最坏时间复杂度和最优时间复杂度都是O(n*log n)，比较稳定。由于需要建立一个堆，所以空间复杂度是n。

为了描述连贯性，以下介绍都已大顶堆为例，小顶堆与之用法相同。

###什么是堆堆通常指二叉堆，其他堆还有斐波那契堆等等。二叉堆首先是一棵二叉树，在此基础上二叉堆的递归定义是这样的：

父节点的值总是大于或等于子节点的值；
每个节点的左子树和右子树也是一个相同类型的二叉堆。

堆排序用到了 堆顶元素永远大于其他元素 和 树调整成堆的时间复杂度是logn 这两个重要性质。

值得注意的是：父节点与子节点间有大小关系，但是左右两个子节点间并没有大小关系，这也是调整成堆时间复杂度较低的原因。

###堆的存储堆的存储和树一样一般存储到数组中，数组下标为i的节点的左子节点下标为2i+1，右子节点下标为2i+2。

###堆排序的实现

有了上述背景，堆排序就很容易实现了。再重复一下堆排序的原理：

利用堆（大顶堆或小顶堆都可）的性质，每次从堆顶取出一个元素放到结果数组中，并删除堆顶元素，然后对堆重新调整，最后完成排序的排序算法。

Ruby版本的实现代码如下：

# 大顶堆调整
def max_heapify(nums, start_i, end_i)
    dad = start_i
    son = 2*start_i + 1
    
    # 开始调整，如果左子节点超过比较范围则无需再比较
    while son < end_i do
        # 选择左右孩子中较大节点，右孩子超出比较范围则无需再比较
        if son+1 < end_i && nums[son] < nums[son+1] then
            son += 1
        end
        
        # 如果当前父节点值小于子节点值则需要调整
        if nums[dad] < nums[son] then
            #swap, pretty awesome, huh~
            nums[dad], nums[son] = nums[son], nums[dad]

            # 转移到下一个父节点
            dad = son
            son = 2*dad + 1
        else
            break
        end
    end
end

这个调整方法容易让人产生困惑。如果在当前nums中start_i位置的节点的左右子树已经是堆的情况下，这个方法可以将start_i为根节点的树调整成堆，但是如果start_i节点下的左右子树并不是堆（子树中可能存在存在比start_i和start_i的左右子节点值都大的值），那么调整后这棵树也未必是堆；

如果非要说这个方法目的那就是：让start_i位置的节点找到自己合适的位置；

这个方法的时间复杂度是以start_i为根节点的树高：log2((end_i - start_i)/2 - 1) + 1。

# 堆排序
def heap_sort(nums)
    if nums.length < 2 then return nums end
    
    # 首先将当前数组调整成堆结构，从最后一个父节点开始调整
    (0..nums.length/2-1).reverse_each do |i|
        max_heapify(nums, i, nums.length)
    end
    
    # 每次将堆顶元素与已排好序的元素之前的那个元素调换，重新调整成堆结构直至根节点
    (0..nums.length-1).reverse_each do |i|
        #another swap, yeah!
        nums[0],nums[i] = nums[i],nums[0]
        
        # 重新调整
        max_heapify(nums, 0, i)
    end
end

这个方法是实现堆排序的主方法，第一步构造一个堆，然后每次循环中有一个元素进入到正确位置。

###堆排序的复杂度

时间复杂度
- 很明显上述算法中的基本操作就是swap，即：a,b=b,a
- 上面已经提到执行一次max_heapify的平均时间复杂度是logn
- heap_sort方法分为两部分
  - 构造堆执行max_heapify方法 n/2 - 1 次
  - 堆排序执行max_heapify方法 n - 1 次

因此总的平均时间复杂度是：O(nlogn) 2. 空间复杂度为：O(1)

堆排序算法的分析就到这里，学习算法的过程需要深入理解算法和涉及到的数据结构的每个细节，注重方法。只有深入理解之后记忆才能永久，有些地方理解不深入的话就会进入遇到一次学一次，学一次忘一次的死循环。

LeetCode实战 - 堆排序

评论 · 0