-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathremoveMin.py
More file actions
72 lines (64 loc) · 1.75 KB
/
removeMin.py
File metadata and controls
72 lines (64 loc) · 1.75 KB
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
__author__ = 'Theo'
#
# Implement remove_min
#
def remove_min(L):
# your code here
L[0] = L[-1]
L.pop()
down_heapify(L, 0)
return L
def parent(i):
return (i-1)/2
def left_child(i):
return 2*i+1
def right_child(i):
return 2*i+2
def is_leaf(L,i):
return (left_child(i) >= len(L)) and (right_child(i) >= len(L))
def one_child(L,i):
return (left_child(i) < len(L)) and (right_child(i) >= len(L))
# Call this routine if the heap rooted at i satisfies the heap property
# *except* perhaps i to its immediate children
def down_heapify(L, i):
# If i is a leaf, heap property holds
if is_leaf(L, i):
return
# If i has one child...
if one_child(L, i):
# check heap property
if L[i] > L[left_child(i)]:
# If it fails, swap, fixing i and its child (a leaf)
(L[i], L[left_child(i)]) = (L[left_child(i)], L[i])
return
# If i has two children...
# check heap property
if min(L[left_child(i)], L[right_child(i)]) >= L[i]:
return
# If it fails, see which child is the smaller
# and swap i's value into that child
# Afterwards, recurse into that child, which might violate
if L[left_child(i)] < L[right_child(i)]:
# Swap into left child
(L[i], L[left_child(i)]) = (L[left_child(i)], L[i])
down_heapify(L, left_child(i))
return
else:
(L[i], L[right_child(i)]) = (L[right_child(i)], L[i])
down_heapify(L, right_child(i))
return
#########
# Testing Code
#
# build_heap
def build_heap(L):
for i in range(len(L)-1, -1, -1):
down_heapify(L, i)
return L
def test():
L = range(10)
build_heap(L)
remove_min(L)
# now, the new minimum should be 1
assert L[0] == 1
test()