二叉堆

二叉堆

二叉堆
二叉堆的逻辑结构是完全二叉树,实际上是由1为起点的一维数组表示。
给定一个节点的下标i,其父节点parent(i)=1/2、左子节点left(i)=2*i、右子节点right(i)=2*i+1。
最大堆性质：节点的键值小于等于其父节点的键值。最大堆堆根中存储着最大的值。
最小堆性质：节点的键值大于等于其父节点的键值。最小堆的根中存储着最小的值。

1.Complete Binary Tree

读取以完全二叉树形式表示的二叉堆，并按照下面的格式输出二叉堆各节点信息
node id: key = k, parent key = pk, left key = lk, right key = rk
输入：第一行堆的大小H。接下来一行，按节点编号顺序输入代表二叉堆节点值的H个整数
输出：按节点编号顺序（1～H）输出代表二叉堆各节点的信息
（挑战程序设计竞赛2算法与数据结构191页例题）

"""
二叉堆
二叉堆的逻辑结构是完全二叉树,实际上是由1为起点的一维数组表示。
给定一个节点的下标`i`,其父节点`parent(i)=1/2`、左子节点`left(i)=2*i`、右子节点`right(i)=2*i+1`。
最大堆性质：节点的键值小于等于其父节点的键值。最大堆堆根中存储着最大的值。
最小堆性质：节点的键值大于等于其父节点的键值。最小堆的根中存储着最小的值。
"""
def parent(i):
    return i//2

def left(i):
    return i*2

def right(i):
    return i*2+1

def solve():
    """
    5                             
    7 8 1 2 3
    node 1: key = 7,  left key = 8,  right key = 1, 
    node 2: key = 8,  parent key = 7,  left key = 2,  right key = 3, 
    node 3: key = 1,  parent key = 7,  
    node 4: key = 2,  parent key = 8,  
    node 5: key = 3,  parent key = 8, 
    """
    H = int(input())
    array = [0]
    array.extend(list(map(int,input().split())))
    for i in range(1,H+1):
        print('node {}: key = {}, '.format(i,array[i]),end=' ')
        if parent(i) >= 1:
            print('parent key = {}, '.format(array[parent(i)]),end=' ')
        if left(i) <= H:
            print('left key = {}, '.format(array[left(i)]),end=' ')
        if right(i) <= H:
            print('right key = {}, '.format(array[right(i)]),end='') 
        print()

if __name__ == '__main__':
    solve()

2.Maximum Heap

使用给定数组生成最大堆。复杂度O(H)
输入：第一行堆的大小H。接下来一行，按节点编号顺序输入代表二叉堆节点值的H个整数
输出：按节点编号顺序（1～H）输出代表二叉堆各节点的值
（挑战程序设计竞赛2算法与数据结构193页例题）

"""
10
4 1 3 2 16 9 10 14 8 7  

16, 14, 10, 8, 7, 9, 3, 2, 4, 1
"""
def left(i):
    return i*2

def right(i):
    return i*2+1

H = 0

def maxHeapify(A,i):
    """
    用于从根节点i向叶节点方向寻找A[i]值的恰当位置,从而使以i为根节点的子树成为最大堆。这里我们假设堆的大小为H
    """
    l = left(i)
    r = right(i)
    largest = None
    if l <= H and A[l] > A[i]:
        largest = l
    else:
        largest = i

    if r <= H and A[r] > A[largest]:
        largest = r
    
    if largest != i :
        A[i],A[largest] = A[largest],A[i]
        maxHeapify(A,largest) # 递归调用
    
def buildMaxHeap(A):
    for i in range(H//2,0,-1):
        # print('i=',i)
        maxHeapify(A,i)

if __name__ == '__main__':
    H = int(input())
    A = [0]
    A.extend(list(map(int,input().split())))
    buildMaxHeap(A)
    print(A)