数据结构 - 堆

介绍堆排序之前，先介绍数据结构 - 堆，堆是一个完全二叉树，并且满足堆的性质：子结点的值总小于（或者大于）其父节点的值。一般来说，堆使用数组来存储，并且根据某个元素在数组中的位置可以推断出其子结点和父节点的位置。

第n个元素(从0开始计数)的左结点是2*n+1，右结点是2*n+2；其父结点是floor((n - 1)/2)

堆排序的思路

根据堆的定义可知，根是堆的最大元素或者最小元素，首先将数组调整为大顶堆，那么第0个元素就是最大元素，将第0个和最后一个元素（暂且称为第n个元素）交换位置，然后再将0~n-1个元素调整为堆，将第0个元素和第n-1元素交换，依次循环下去~

听起来很复杂，但只要花点时间，读完这篇文章，一定可以明白堆排序，下面一点点拆解~

如何将数组调整为堆

思路：从最后一个结点的父节点开始处理，假设一共有n个元素，那么最后一个结点的父节点是第(n-1)/2个元素，找到其子节点中值最大的节点，然后根其自身比较，如果自身值比子节点小，那么交换位置。

循环上述过程，从第(n-1)/2 一直遍历到第0个元素就完成了堆的构建。

Python代码如下所示：

def make_heap(array):
last_p = (len(array)-1)/2
while(last_p>=0):
child = 2*last_p+1
if(child+1 < len(array)):
if(array[child] < array[child+1]):
child = child+1
if(child < len(array) and array[child] > array[last_p]):
tmp = array[last_p]
array[last_p] = array[child]
array[child] = tmp
last_p=last_p-1
print(array[0])

完整逻辑

构建堆是堆排序中重要环节之一，构建完堆之后应该将第0个元素和最后一个元素交换位置，然后将前n-1个元素构建堆，再将第0个和倒数第二个交换...

其中涉及到一些细节，只有自己亲自动手编码才能掌握了解，这里给出一份DEMO

完整代码如下：

# -*- coding: UTF-8 -*-
 
import math
 
def make_heap(array,n):
 
last_p = (n-1)/2
 
while(last_p>=0):
 
child = 2*last_p+1
 
if(child+1 < n):
 
if(array[child] < array[child+1]):
 
child = child+1
 
if(child < n and array[child] > array[last_p]):
 
tmp = array[last_p]
 
array[last_p] = array[child]
 
array[child] = tmp
 
last_p=last_p-1
 
def swap_i_j(array,i,j):
 
array[i],array[j] = array[j],array[i]
 
def heap_sort(array):
 
n = len(array)
 
while(n>0):
 
make_heap(array,n)
 
print(n,array)
 
swap_i_j(array,0,n-1)
 
print(n,array)
 
n = n-1
 
array = [16,7,8,20,17,3]
 
heap_sort(array)
 
print(array)

输出结果：