二叉堆
什么是二叉堆？ 二叉堆本质上是一种完全二叉树，它分为两个类型。 1. 最大堆。 2. 最小堆。
什么是最大堆呢？最大堆的任何一个父节点的值，都大于或等于 它 左、右孩子节点的值
什么是最小堆呢？最小堆的任何一个父节点的值，都小于或等于它左、 右孩子节点的值。
二叉堆的根节点叫作堆顶 。 最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素 ；最小堆的堆顶是整个堆中的最小元素 。
插入节点
当二叉堆插入节点时，插入位置是完全二叉树的最后一个位置。例如插 入一个新节点，值是 0。 这时，新节点的父节点5比0大，显然不符合最小堆的性质。于是让新节 点“上浮”，和父节点交换位置。 继续用节点0和父节点3做比较，因为0小于3，则让新节点继续“上浮”。 继续比较，最终新节点0“上浮”到了堆顶位置。
删除节点
二叉堆删除节点的过程和插入节点的过程正好相反，所删除的是处于堆 顶的节点。例如删除最小堆的堆顶节点1。 这时，为了继续维持完全二叉树的结构，我们把堆的最后一个节点10临 时补到原本堆顶的位置。 接下来，让暂处堆顶位置的节点10和它的左、右孩子进行比较，如果 左、右孩子节点中最小的一个（显然是节点2）比节点10小，那么让节 点10“下沉”。 继续让节点10和它的左、右孩子做比较，左、右孩子中最小的是节点 7，由于10大于7，让节点10继续“下沉”。 这样一来，二叉堆重新得到了调整。
构建二叉堆
构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质就是 让所有非叶子节点依次“下沉” 。 下面举一个无序完全二叉树的例子。 首先，从最后一个非叶子节点开始，也就是从节点10开始。如果节点10 大于它左、右孩子节点中最小的一个，则节点10“下沉”。 接下来轮到节点3，如果节点3大于它左、右孩子节点中最小的一个，则 节点3“下沉”。 然后轮到节点1，如果节点1大于它左、右孩子节点中最小的一个，则节 点1“下沉”。事实上节点1小于它的左、右孩子，所以不用改变。 接下来轮到节点7，如果节点7大于它左、右孩子节点中最小的一个，则 节点7“下沉”。 节点7继续比较，继续“下沉”。 经过上述几轮比较和“下沉”操作，最终每一节点都小于它的左、右孩子 节点，一个无序的完全二叉树就被构建成了一个最小堆。
二叉堆虽然是一个完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉 堆的所有节点都存储在数组中
假设父节点的下标是parent，那么它的左孩子下标就是 2×parent+1 ；右 孩子下标就是2×parent+2 。
堆排序算法
把无序数组构建成二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆。
循环删除堆顶元素，替换到二叉堆的末尾，调整堆产生新的堆顶
# -*- coding: utf-8 -*-
"""
Created on Wed Dec 8 21:38:45 2021
@author: Binbincome
"""
def heap_sort(array=[]):
# 1.无序数组构建成最大堆
for i in range((len(array)-2)//2,-1,-1):
down_adjust(i, len(array), array)
# 2.循环交换集合尾部到堆顶，并调节堆产生新得堆顶
for i in range(len(array)-1, 0 , -1):
# 最后一个元素和第一个元素进行交换
temp = array[i]
array[i] = array[0]
array[0] = temp
# 下沉调整最大堆
down_adjust(0, i, array)
def down_adjust(parent_index, length, array=[]):
# temp保存父节点得值，最后赋值
temp = array[parent_index]
child_index = 2*parent_index+1
while child_index<length:
# 如果有右孩子，且右大于左，定位到右
if child_index+1<length and array[child_index+1]>array[child_index]:
child_index+=1
# 如果父节点值大于等于任何一个孩子得值就直接跳出
if temp >= array[child_index]:
break
# 无需真正交换，单向赋值即可
array[parent_index]=array[child_index]
parent_index = child_index
child_index = 2*child_index+2
array[parent_index] = temp
my_array = list([2,23,45,65,2,5,74,2,-6,-7,0,2,11])
heap_sort(my_array)
print(my_array) 整体时间复杂度为O(nlog(n))
