侯瑞哲的博客

Ruizhe's Blog

0%

堆的实现(大顶堆、小顶堆)

发表于 更新于 Valine： 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
# 堆的实现.py


# 大顶堆
def maxheap(a, i, size):
    l = 2 * i + 1
    r = 2 * i + 2
    large = i
    if l < size and a[l] > a[large]:
        large = l
    if r < size and a[r] > a[large]:
        large = r
    if large != i:
        a[i], a[large] = a[large], a[i]
        maxheap(a, large, size)


def buildheap(a, size):
    for i in range(size >> 1, -1, -1):
        maxheap(a, i, size)


def insert(a, val, size):
    a.append(val)
    assert a[size - 1] == val
    i = size - 1
    p = i >> 1
    while p >= 0 and a[p] < a[i]:
        a[p], a[i] = a[i], a[p]
        i = p
        p = i >> 1


# 小顶堆
# def minheap(a, i, size):
#     l = 2 * i + 1
#     r = 2 * i + 2
#     small = i
#     if l < size and a[l] < a[small]:
#         small = l
#     if r < size and a[r] < a[small]:
#         small = r
#     if small != i:
#         a[i], a[small] = a[small], a[i]
#         minheap(a, small, size)
#
#
# def buildheap(a, size):
#     for i in range(size >> 1, -1, -1):
#         minheap(a, i, size)


def main():
    # 示例
    nums = [3, 2, 5, 1, 4]
    heapsize = len(nums)

    # 建堆
    buildheap(nums, heapsize)
    print(nums)
    # output:
    # [5, 4, 3, 1, 2]

    # 插入
    # nums.append(6)
    # heapsize += 1
    # i = heapsize - 1
    # while i >> 1 >= 0 and nums[i] > nums[i >> 1]:
    #     nums[i], nums[i >> 1] = nums[i >> 1], nums[i]
    #     i >>= 1
    # print(nums)
    heapsize += 1
    insert(nums, 6, heapsize)
    print(nums)
    # output:
    # [6, 5, 4, 1, 2, 3]

    # 删除
    heapsize -= 1
    nums[0], nums[heapsize] = nums[heapsize], nums[0]
    maxheap(nums, 0, heapsize)
    print(nums)

    # output:
    # [5, 2, 3, 1, 0, 4]


if __name__ == '__main__':
    main()