-
Notifications
You must be signed in to change notification settings - Fork 0
/
pairing_heap_standard.py
209 lines (195 loc) · 6.13 KB
/
pairing_heap_standard.py
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#!/usr/bin/python3
from node import Node
from pairing_heap_interface import PairingHeapInterface
class PairingHeapStandard(PairingHeapInterface):
"""standard pairing heap
performs a left-to-right forward pass, then a backward combining pass to consolidate"""
updates = 0
def __init__(self, root=None):
self.root = root
self.updates += 1
def make_heap(self):
# this is equivalent to init
pass
def listInorder(self, root):
if (root is None):
return []
return self.listInorder(root.leftChild) + [root.key] + self.listInorder(root.nextSibling)
def find_min(self):
if self.root is None:
return None
else:
return self.root
def insert(self, node):
""" inserts node by linking to current root,
returns number of link operations"""
linkCount = 0
if self.root is None:
# heap was empty before
self.root = node
self.updates += 1
else:
newheap = PairingHeapStandard(node)
linkCount = self.merge(newheap)
# print(self.listInorder(self.root))
return linkCount
def delete_min(self):
"""Extracts minimum (current root), consolidates orphaned children.
returns number of link operations"""
linkCount = 0 # counts number of linking operations
minNode = None
if self.root is None:
print("Heap was already empty.")
return (minNode, linkCount)
elif self.root.leftChild is None:
# heap contained only one element
minNode = self.root
self.root = None
self.updates += 1
return (minNode, linkCount)
elif self.root.leftChild.nextSibling is None:
# first child has no siblings->first child becomes root
minNode = self.root
self.root = self.root.leftChild
self.updates += 1
self.root.parent = None
self.updates += 1
return (minNode, linkCount)
else:
minNode = self.root
self.root = self.root.leftChild
self.updates += 1
current = self.root
nextSibling = None
heaps = []
paired = []
# left-to-right pairing pass
while current is not None: # create heaps of all orphaned children
nextSibling = current.nextSibling
heaps += [PairingHeapStandard(current)]
current.nextSibling = None
self.updates += 1
current = nextSibling
for j in range(0, len(heaps), 2):
if j == (len(heaps) - 1): # last one
paired += [heaps[j]]
else:
heap = heaps[j]
linkCount += heap.merge(heaps[j + 1]) # merge returns its number of link operations
paired += [heap]
# combining backwards (right-to-left) pass
combined = paired[-1] # start with last (rightmost) tree
for i in range(len(paired) - 2, -1, -1):
linkCount += combined.merge(paired[i]) # merge returns its number of link operations
self.root = combined.root
self.updates += 1
self.root.parent = None
self.updates += 1
return (minNode, linkCount)
def merge(self, heap2):
"""merges heap2 with current heap by linking roots.
returns number of link operations"""
linkCount = 0 # counts number of linking operations
if self.root is None: # heap is empty
self.root = heap2.root
self.updates += 1
elif heap2.root is None: # heap 2 is empty
pass # this heap is the result
else:
# link roots
if self.root.key <= heap2.root.key:
heap2.root.nextSibling = self.root.leftChild
self.updates += 1
if heap2.root.nextSibling is None:
heap2.root.parent = self.root
self.updates += 1
self.root.leftChild = heap2.root
self.updates += 1
linkCount = 1
else:
self.root.nextSibling = heap2.root.leftChild
self.updates += 1
if self.root.nextSibling is None:
self.root.parent = heap2.root
self.updates += 1
heap2.root.leftChild = self.root
self.updates += 1
self.root = heap2.root
self.updates += 1
linkCount = 1
return linkCount
def decrease_key(self, node, diff):
"""cuts node with subtree from current place in tree;
decreases key; links node to root"""
linkCount = 0
if self.root == node:
self.root.key = self.root.key - diff
self.updates += 1
else:
# first step: cut node from heap
self.unlink_node(node) # helper function
# second step: decrease key
subheap = PairingHeapStandard(node)
subheap.root.key = subheap.root.key - diff
self.updates += 1
# third step: merge back in
linkCount = self.merge(subheap)
return linkCount
def delete(self, node):
"""removes node with subtree from current place in tree;
deletes node, consolidating orphaned children;
links consolidated subtree to root.
returns number of link operations"""
if node is None:
return 0
if self.root.key == node.key:
(minNode, lc) = self.delete_min()
return lc
else:
self.unlink_node(node) # helper function
subheap = PairingHeapStandard(node)
linkCount = subheap.delete_min()
linkCount += self.merge(subheap)
return linkCount
def unlink_node(self, node):
"""removes node from heap, updating pointers accordingly"""
if self.root == node: # remove the whole heap
self.root = None
self.updates += 1
else:
if node.nextSibling != None:
temp = node.nextSibling
while temp.nextSibling != None:
temp = temp.nextSibling
if temp.parent.leftChild == node: # node is leftmost child
# link parent to next sibling
temp.parent.leftChild = node.nextSibling
self.updates += 1
node.nextSibling = None
self.updates += 1
else:
# node is neither first nor last child of parent
prevSibling = temp.parent.leftChild
while prevSibling.nextSibling != node: # find left (previous) sibling
prevSibling = prevSibling.nextSibling
self.updates += 1
prevSibling.nextSibling = node.nextSibling # cut out node, link left and right sibling
self.updates += 1
else:
# node is rightmost child of parent
if node.parent.leftChild == node:
# node is only child: just remove
node.parent.leftChild = None
self.updates += 1
else:
prevSibling = node.parent.leftChild
while prevSibling.nextSibling != node: # find left (previous) sibling
prevSibling = prevSibling.nextSibling
prevSibling.parent = node.parent
self.updates += 1
prevSibling.nextSibling = None
self.updates += 1
node.parent = None
self.updates += 1
def pointer_updates(self):
return self.updates