堆以及堆排序

堆的定义，
以大顶堆为例，需要满足两个条件：

1. 堆是一颗完全二叉树
2. 堆的每一个节点的值都必须大于等于其子树中每个节点的值。或者等价表述为，堆中每个节点的值都大于等于其左右子节点的值。

堆的建立

堆是一颗完全二叉树，完全二叉树非常适合数组存储，所以一般而言，堆都是用数组的形式存储的。
此处假设，堆的第一个元素存储在数组下标为1的地方，则对于任意的节点i，其左子节点为2i，其右子节点为2i+1，父节点为i/2.
若堆中的数据从数组下标为0的地方开始存储，则对于任意的节点i，其左子节点为2i+1, 其右子节点为2i+2， 父节点为(i-1)/2.

建堆的过程是要将一个数组转化为满足要求的堆。一般建堆有两种思路，
① 借用插入元素的思想。假设已经存在一个满足条件的堆，然后从数组中的第二个元素开始，不断的插入一个元素，每插入一个元素，进行调整即可。
② 从第一个非根叶子节点开始堆化，直到根节点。

def buildHeap(heap_list):
    lenght = len(heap_list)
    for i in range(lenght//2, 0, -1):
        heapify(heap_list, len(heap_list), i)

def heapify(heap_list, n, i):
    """
    将i节点作为根节点的子树从上到下进行调整
    """
    lenght = n
    while True:
        # max_index 记录当前i所在的子树中最大值的节点编号
        max_index = i
        if 2*i < lenght and heap_list[2*i] > heap_list[max_index]:
            max_index = 2*i
        if 2*i + 1< lenght and heap_list[2*i+1] > heap_list[max_index]:
            max_index = 2*i + 1
        # 若当前节点已经比左右子节点大了，表明已经不需要向下堆化了。
        if max_index == i:
            break
        heap_list[max_index], heap_list[i] = heap_list[i], heap_list[max_index]
        i = max_index

②堆排序

def heapSort(heap_list):
    if len(heap_list) <=2:
        return
    buildHeap(heap_list)
    for i in range(len(heap_list)-1, 1, -1):
        heap_list[1], heap_list[i] = heap_list[i], heap_list[1]
        heapify(heap_list, i, 1)

③插入和删除

def delete(heap_list):
    """
    删除堆顶元素
    此处先建堆，然后将堆顶元素与最后一个元素交换，然后从堆顶元素自顶向下堆化
    """
    length = len(heap_list)
    # buildHeap(heap_list)
    heap_list[1], heap_list[length-1] = heap_list[length-1], heap_list[1]
    heapify(heap_list, length-1, 1)

def insert(heap_list, data):
    """
    向堆heap_list中插入元素data
    先将元素data放置在最后，然后自下而上的堆化
    """
    heap_list.append(data)
    length = len(heap_list)
    i = length-1
    while i > 1:
        if i//2 >= 1 and heap_list[i] > heap_list[i//2]:
            heap_list[i], heap_list[i//2] = heap_list[i//2], heap_list[i]
            i = i//2
        else:
            break
    

if __name__ == '__main__':
    test_case = [0, 7,5,19,8,4,1,20,13,16]
    buildHeap(test_case)
    print('test_case', test_case)

    insert(test_case, 21)   
    print('test_case', test_case)