A Heap is a collection of data points that are organized to allow quick
access to either the minimum or maximum element. The Heap shown above is
a "Max Heap", meaning that the maximum value is at the root (top) node.
The key idea (rule) behind a Max Heap is that every node in the tree is
greater than or equal to than all nodes below it.
This rule is known as the "Heap Condition".
As each additional point is added to the Heap, it must be compared to the node
above it, known as its parent node.
If the child node is greater than the parent node, the two must be exchanged.
If the nodes are exchanged, the new parent node must be compared with its
parent node, and so on, until the Heap Condition is satisfied all the way to
the root (top) node.
In the data set above, there are 31 elements.
So here we have 5 letters of the alphabet that are repeated.
If both the child and parent are the same letter, no elements need to
be exchanged because the Heap Condition is already satisfied.
Note that the Heap Condition applies to both child nodes equally, and there
is no requirement that either the left or right child is greater than the other.
After the Heap above has been fully constructed, the root node will always be Z.
One of the children will always be Y.
However, X can either be a direct child of Z or a child of Y.
The number of operations required to maintain the Heap Condition is at most
equal to to the height of the tree.
A little bit of math is needed to reveal the relationship between the total
number of nodes and the number of levels (height) of the Heap.
Notice how the number of nodes at each level of the tree
doubles as you go down the tree: the first level has 1 node = 20,
the second level has 2 nodes = 21, the third level has 4 nodes =
22, etc. The exponent of 2 is one less than the number of levels, so
if there are "k" levels, the final level has 2k-1 nodes.
For the tree above, N = sum of nodes at each level = 1 (first level) +
2 (second level) + 4 (third level) +
8 (fourth level) + 16 (fifth level) = 20 + 21 +
22 + 23 + 24 = 31.
So we can express N in terms of 2 raised to some exponent (actually, k-1).
The inverse operation of exponentiation is, by definition, the logarithm.
So let's just plug this into our calculator: log2N = log231 = 4.95,
Now we already know that the number of levels k = 5.
From this calculation, we find that k = next highest integer than log2N.
The whole point of this calculation is so show that for a Heap of any size
N, the height of the tree "k" = next greatest integer than log2N.
Thus for a Heap of any size N, the number of operations required to maintain
the Heap Conditions = log2N + 1.
If we want to organize a very large number of elements in a Heap, the addition
of each new element requires only log2N + 1 operations.
This is far less than if we were to maintain an ordered array, which would
require, on average, N/2 operations to add a new element and find its correct position.
Python Program for a Heap and a Indexed Heap (also known as a
Priority Queue)
(This Python module also includes some functions to test their operation)
'''
class MinHeap
class MaxHeap
'''
import math
import random
class max_heap:
def __init__(self):
'''
To make index arithmetic simple, the array a is one-indexed,
i.e. a[0] = None
'''
self.a = [None]
self.N = 0
def __sink(self, k):
'''
k = parent index
k2 = child index, initially left child
'''
k2 = 2 * k
# Loop while the child index is before the end of the array
while (k2 <= self.N):
# If a right child exists, change the child index to the right child
if (k2 < self.N) and (self.a[k2] < self.a[k2+1]):
k2 += 1
# Exchange if child is greater than parent
if self.a[k] < self.a[k2]:
(self.a[k2], self.a[k]) = (self.a[k], self.a[k2])
k = k2
k2 *= 2
def heapify(self, input_list):
'''
input_list is 0-indexed
internal list self.a is 1-indexed
self.a[1] = first element
self.a[self.N] = last element
'''
self.N = len(input_list)
# Append the input list to [None]
self.a = [None] + input_list
# Sink all elements starting from the end of the second
# to last row
k = self.N / 2
for k in range(k, 0, -1):
self.__sink(k)
def __swim(self, k):
# p = parent index
p = k/2
while p > 0:
# If the parent is less, exchange
if self.a[p] < self.a[k]:
(self.a[p], self.a[k]) = (self.a[k], self.a[p])
k = p
p = k/2
def insert(self, value):
'''
Add the element to the end and swim
'''
self.N += 1
self.a.append(value)
self.__swim(self.N)
def max(self):
return self.a[1]
def remove_max(self):
'''
Element 1 is the max
Exchange with last element
Decrement size
Sink first element
Return last element
'''
(self.a[self.N], self.a[1]) = (self.a[1], self.a[self.N])
self.N -= 1
self.__sink(1)
return self.a.pop()
def sort_down(self):
'''
sorts list in place
loop starting at the top index
exchange with last element
sink down top element
'''
for k in range(1, self.N):
# Exchange to place the largest element remaining at the end
(self.a[1], self.a[self.N]) = (self.a[self.N], self.a[1])
# Decrement the length of the remaining elements
self.N -= 1
# Sink the new top element
self.__sink(1)
self.N = len(self.a) - 1
def print_heap_simple(self):
for i in range(1, self.N + 1):
print "a[%d] = %d" % (i, self.a[i])
def print_heap(self):
#print "\nheap N = %d" % self.N
#print "\nheap"
k = 1
k2 = 2 * k
# number of characters to print
key_width = 2
min_space = 2
if self.N == 0:
return
elif self.N == 1:
depth = 1
else:
depth = math.floor(math.log(self.N - 1, 2)) + 1
leaves = 2**(depth - 1)
format = "%" + str(key_width) + "d"
# 1 is the spacing between entries on the bottom row
bottom_width = leaves * (min_space + key_width)
indent_width = bottom_width
indent_float = float(bottom_width)
'''
12345678901234567890123457689012
----------------xx indent = 16
--------xx--------------xx indent = 8, spacing = 14
----xx------xx------xx------xx indent = 4, spacing = 6
--xx--xx--xx--xx--xx--xx--xx--xx indent = 2, spacing = 2
'''
while k <= self.N:
#row_leaves = 2**(k-1)
#row_gap = 2 * (depth - k + 1) - 1
indent_float = indent_float / 2.0
indent_width = int(math.floor(indent_float))
indent = " " * int(indent_width)
spacing = " " * (indent_width * 2 - 2)
if k2 > self.N:
k2 = self.N + 1
pstring = indent
for i in range(k, k2):
heap_i = self.a[i]
if heap_i or heap_i == 0:
pstring += format % heap_i + spacing
else:
pstring += "None "
print pstring
k = k2
k2 = 2 * k
def test_max_heap_1():
a = [5, 3, 4, 1, 7, 2, 6]
max_h = max_heap()
max_h.heapify(a)
max_h.print_heap()
max_h.sort_down()
print "after sort_down:"
max_h.print_heap()
def test_max_heap_2():
N = 16
a = range(1, N)
random.shuffle(a)
print "input list:"
print repr(a)
print "heap:"
max_h = max_heap()
for i in range(0, len(a)):
max_h.insert(a[i])
max_h.print_heap()
max_h.sort_down()
print "after sort_down:"
max_h.print_heap()
def test_max_heap_3():
'''
tests insert and remove_max
'''
use_random = False
if use_random:
N = 13
a = range(1, N+1)
random.shuffle(a)
else:
N = 3
a = [3, 2, 1]
print "input list:"
print repr(a)
print "heap:"
max_h = max_heap()
for i in range(0, len(a)):
print "insert %d" % a[i]
max_h.insert(a[i])
max_h.print_heap()
#max_h.print_heap()
print "remove max:"
for i in range(0, len(a)):
max_value = max_h.remove_max()
print "%d" % max_value
max_h.print_heap()
class min_heap:
def __init__(self):
'''
To make index arithmetic simple, the array a is one-indexed,
i.e. a[0] = None
'''
self.a = [None]
self.N = 0
def __sink(self, k):
'''
k = parent index
k2 = child index, initially left child
'''
k2 = 2 * k
# Loop while the child index is before the end of the array
while (k2 <= self.N):
# If a right child exists, change the child index to the right child
if (k2 < self.N) and (self.a[k2] > self.a[k2+1]):
k2 += 1
# Exchange if child is greater than parent
if self.a[k] > self.a[k2]:
(self.a[k2], self.a[k]) = (self.a[k], self.a[k2])
k = k2
k2 *= 2
def heapify(self, input_list):
'''
input_list is 0-indexed
internal list self.a is 1-indexed
self.a[1] = first element
self.a[self.N] = last element
'''
self.N = len(input_list)
# Append the input list to [None]
self.a = [None] + input_list
# Sink all elements starting from the end of the second
# to last row
k = self.N / 2
for k in range(k, 0, -1):
self.__sink(k)
def __swim(self, k):
# p = parent index
p = k/2
while p > 0:
# If the parent is less, exchange
if self.a[p] > self.a[k]:
(self.a[p], self.a[k]) = (self.a[k], self.a[p])
k = p
p = k/2
def insert(self, value):
'''
Add the element to the end and swim
'''
self.N += 1
self.a.append(value)
self.__swim(self.N)
def min(self):
return self.a[1]
def remove_min(self):
'''
Element 1 is the min
Exchange with last element
Decrement size
Sink first element
Return last element
'''
(self.a[self.N], self.a[1]) = (self.a[1], self.a[self.N])
self.N -= 1
self.__sink(1)
#self.print_heap()
return self.a.pop()
def sort_down(self):
'''
sorts list in place
loop starting at the top index
exchange with last element
sink down top element
'''
for k in range(1, self.N):
# Exchange to place the largest element remaining at the end
(self.a[1], self.a[self.N]) = (self.a[self.N], self.a[1])
# Decrement the length of the remaining elements
self.N -= 1
# Sink the new top element
self.__sink(1)
self.N = len(self.a) - 1
def print_heap_simple(self):
for i in range(1, self.N + 1):
print "a[%d] = %d" % (i, self.a[i])
def print_heap(self):
#print "\nheap N = %d" % self.N
#print "\nheap"
k = 1
k2 = 2 * k
# number of characters to print
key_width = 2
min_space = 2
if self.N == 0:
return
elif self.N == 1:
depth = 1
else:
depth = math.floor(math.log(self.N - 1, 2)) + 1
leaves = 2**(depth - 1)
format = "%" + str(key_width) + "d"
# 1 is the spacing between entries on the bottom row
bottom_width = leaves * (min_space + key_width)
indent_width = bottom_width
indent_float = float(bottom_width)
'''
12345678901234567890123457689012
----------------xx indent = 16
--------xx--------------xx indent = 8, spacing = 14
----xx------xx------xx------xx indent = 4, spacing = 6
--xx--xx--xx--xx--xx--xx--xx--xx indent = 2, spacing = 2
'''
while k <= self.N:
#row_leaves = 2**(k-1)
#row_gap = 2 * (depth - k + 1) - 1
indent_float = indent_float / 2.0
indent_width = int(math.floor(indent_float))
indent = " " * int(indent_width)
spacing = " " * (indent_width * 2 - 2)
if k2 > self.N:
k2 = self.N + 1
pstring = indent
for i in range(k, k2):
heap_i = self.a[i]
if heap_i or heap_i == 0:
pstring += format % heap_i + spacing
else:
pstring += "None "
print pstring
k = k2
k2 = 2 * k
def test_min_heap_3():
N = 13
a = range(1, N+1)
random.shuffle(a)
print "input list:"
print repr(a)
print "heap:"
min_h = min_heap()
for i in range(0, len(a)):
min_h.insert(a[i])
min_h.print_heap()
print "remove min:"
for i in range(0, len(a)):
min_value = min_h.remove_min()
print "min(%d) = %d" % (i, min_value)
min_h.print_heap()
class indexed_max_heap:
def __init__(self, NMAX):
'''
Data structure that allows max key to be accessed, or
key can be found in the heap according to the value of
key_index provided when using the insert method.
keys[i] = key
pq is the priority queue
pq[1] = i_max (i that corresponds to index of maximum key)
pq[j] maintains the heap condition for jth index of keys
qp[i] -> position of index i in pq
0 <= i <= NMAX
therefore, the arrays are sized to NMAX + 1 length
'''
self.NMAX = NMAX
self.N = 0
self.keys = [None] * (self.NMAX + 1)
self.pq = [None] * (self.NMAX + 1)
self.qp = [None] * (self.NMAX + 1)
def is_empty(self):
return self.N == 0
def __sink(self, k):
'''
k = parent index
k2 = child index, initially left child
'''
k2 = 2 * k
# Loop while the child index is before the end of the array
while (k2 <= self.N):
# If a right child exists, change the child index to the right child
if (k2 < self.N) and (self._less(k2, k2+1)):
# k2+1 is greater, so use that index for comparison
# i.e, k2+1 is the greater child
k2 += 1
# Exchange if child is greater than parent
if self._less(k, k2):
#(self.a[k2], self.a[k]) = (self.a[k], self.a[k2])
self.__exchange(k, k2)
k = k2
k2 *= 2
def heapify(self, input_list):
'''
input_list is 0-indexed
internal list self.a is 1-indexed
self.a[1] = first element
self.a[self.N] = last element
'''
self.N = len(input_list)
# Append the input list to [None]
self.a = [None] + input_list
# Sink all elements starting from the end of the second
# to last row
k = self.N / 2
for k in range(k, 0, -1):
self.__sink(k)
def __swim(self, k):
# p = parent index
p = k/2
while p > 0:
# If the parent is less, exchange
if self._less(p, k):
self.__exchange(p, k)
k = p
p = k/2
# Use only one underscore to prevent name-mangling for subclasses
def _less(self, p, q):
'''
p and q are heap positions
'''
return self.keys[self.pq[p]] < self.keys[self.pq[q]]
# Use only one underscore to prevent name-mangling for subclasses
def _less_val(self, value1, value2):
'''
This method is used when change the key values
'''
return value1 < value2
def __exchange(self, p, q):
'''
p and q are positions in the heap
'''
#print "exchange(%d, %d)" % (p, q)
(self.pq[p], self.pq[q]) = (self.pq[q], self.pq[p])
# Update the reverse mapping from index to heap position
self.qp[self.pq[p]] = p
self.qp[self.pq[q]] = q
def insert(self, i, key):
'''
Add the element to the end and swim
i -> key_index
'''
if i < 0 or i > self.NMAX:
raise ValueError("indexed_max_heap.insert: key %d is out of range" % i)
#print "insert(%d, %d)" % (key_index, key)
self.keys[i] = key
self.N += 1
self.pq[self.N] = i
self.qp[i] = self.N
self.__swim(self.N)
#self.print_heap()
def get_max_key(self):
return self.keys[self.pq[1]]
def get_max_index(self):
return self.pq[1]
def remove_max(self):
'''
Element 1 is the max
Exchange with last element
Decrement size
Sink first element
Return index of the max_key
Call get_max_key before remove_max if you need it's value
'''
index = self.pq[1]
max_key = self.keys[index]
print_info = False
if print_info:
print "remove_max: key[%d] = %d" % (index, max_key)
self.__exchange(1, self.N)
# remove last element from the heap
self.pq[self.N] = None
# Decrease heap size
self.N -= 1
self.__sink(1)
# remove reverse index to the heap
self.qp[index] = None
return index
def remove(self, i):
'''
Find position of i in the heap, then exchange with last heap index
Then maintain heap condition (max is at top):
Sink that position if the key decreased
Swim that position if the key increased
'''
if not self.contains(i):
raise ValueError ("indexed_map_heap.remove error: invalid key_index = %d" % i)
# Look up the heap position
index = self.qp[i]
# Exchange with end of heap
self.__exchange(index, self.N)
# Save the key to return
key = self.keys[index]
# Check if the key increased or decreased
if self._less(index, self.N):
self.N -= 1
# The key has decreased, so sink
self.__sink(index)
else:
self.N -= 1
self.__swim(index)
# Remove the key
self.keys[i] = None
# Remove the reverse mapping
self.qp[i] = None
# Now remove the end of the heap
self.pq[self.N + 1] = None
return key
def change(self, i, new_key):
'''
change the key at i
if the new_key is less than the old_key, then sink
if the new_key is not less than the old_key, then swim
'''
if not self.contains(i):
raise ValueError ("indexed_map_heap.change error: invalid key_index = %d" % i)
old_key = self.keys[i]
# Get the position in the heap
index = self.qp[i]
self.keys[i] = new_key
if self._less_val(new_key, old_key):
self.__sink(index)
else:
self.__swim(index)
def contains(self, i):
if i < 0 or i > self.NMAX + 1:
raise ValueError("indexed_max_heap.contains error: invalid key_index = %d" % i)
if self.keys[i]:
return True
return False
def sort_down(self):
'''
sorts list in place
loop starting at the top index
exchange with last element
sink down top element
'''
n_orig = self.N
for k in range(1, self.N):
# Exchange to place the largest element remaining at the end
#(self.a[1], self.a[self.N]) = (self.a[self.N], self.a[1])
self.__exchange(1, self.N)
# Decrement the length of the remaining elements
self.N -= 1
# Sink the new top element
self.__sink(1)
self.N = n_orig
def print_heap(self):
#print "\nheap N = %d" % self.N
print "\nheap"
k = 1
k2 = 2 * k
# number of characters to print
key_width = 2
min_space = 2
if self.N == 0:
return
elif self.N == 1:
depth = 1
else:
depth = math.floor(math.log(self.N - 1, 2)) + 1
leaves = 2**(depth - 1)
format = "%" + str(key_width) + "d"
# 1 is the spacing between entries on the bottom row
bottom_width = leaves * (min_space + key_width)
indent_width = bottom_width
indent_float = float(bottom_width)
'''
12345678901234567890123457689012
----------------xx indent = 16
--------xx--------------xx indent = 8, spacing = 14
----xx------xx------xx------xx indent = 4, spacing = 6
--xx--xx--xx--xx--xx--xx--xx--xx indent = 2, spacing = 2
'''
while k <= self.N:
#row_leaves = 2**(k-1)
#row_gap = 2 * (depth - k + 1) - 1
indent_float = indent_float / 2.0
indent_width = int(math.floor(indent_float))
indent = " " * int(indent_width)
spacing = " " * (indent_width * 2 - 2)
if k2 > self.N:
k2 = self.N + 1
pstring = indent
for i in range(k, k2):
heap_i = self.pq[i]
key = self.keys[heap_i]
if key:
pstring += format % key + spacing
else:
pstring += "None "
print pstring
k = k2
k2 = 2 * k
print_heap_index = False
if print_heap_index:
print "\ni, heap index"
for i in range(1, self.N+1):
index = self.pq[i]
key = self.keys[index]
print "pq[%d] = %d, key[%d] - %d" % (i, index, index, key)
'''
print "\nheap"
for i in range(1, self.N+1):
print "heap[%d] = %d" % (i, self.keys[self.key_index[i]])
'''
def test_indexed_max_heap_3():
use_random = True
if use_random:
N = 15
a = range(1, N+1)
random.shuffle(a)
else:
a = [3, 5, 6, 4, 1, 7, 2]
print "input list:"
print repr(a)
max_h = indexed_max_heap()
for i in range(0, len(a)):
max_h.insert(i, a[i])
max_h.print_heap()
#max_h.remove_max()
max_h.remove(0)
max_h.print_heap()
'''
print "remove max:"
for i in range(0, len(a)):
max_value = max_h.remove_max()
print "%d" % max_value
'''
class indexed_min_heap(indexed_max_heap):
def remove_max(self):
raise
def remove_min(self):
return indexed_max_heap.remove_max(self)
def _less(self, p, q):
'''
OPPOSITE comparison for min_heap
p and q are heap indexes
'''
return self.keys[self.pq[p]] > self.keys[self.pq[q]]
def _less_val(self, value1, value2):
'''
OPPOSITE comparison for min_heap
'''
return value1 > value2
def test_indexed_min_heap_3():
use_random = False
i_remove = 0
if use_random:
N = 31
a = range(1, N+1)
random.shuffle(a)
else:
#a = [3, 5, 6, 4, 1, 7, 2]
old_key = 2
a = [2, 7, 10, 13, 14, 6, 15, 9, 12, 1, 5, 4, 8, 11, 3]
#a = [21, 27, 25, 5, 1, 17, 15, 11, 19, 31, 26, 24, 22, 8, 6, 4, 13, 9, 10, 28, 16, 18, 20, 14, 7, 23, 30, 12, 3, 29, 2]
#old_key = 30
i_remove = a.index(old_key)
print "remove a[%d] = %d" % (i_remove, old_key)
print "input list:"
print repr(a)
min_h = indexed_min_heap()
for i in range(0, len(a)):
min_h.insert(i, a[i])
min_h.print_heap()
#max_h.remove_max()
min_h.remove(i_remove)
min_h.print_heap()
class indexed_max_heap_dict:
def __init__(self):
raise ValueError("This class has not been tested with duplicate keys")
'''
Data structure that allows max key to be accessed, or
key can be found in the heap according to the value of
key_index provided when using the insert method. An optional
value can be associated with each key_index.
'''
#self.keys = []
#self.values = []
self.keys = {}
self.values = {}
self.N = 0
#self.key_index = [None]
self.key_index = {}
self.heap_index = [None]
def is_empty(self):
return self.N == 0
def __sink(self, k):
'''
k = parent index
k2 = child index, initially left child
'''
k2 = 2 * k
# Loop while the child index is before the end of the array
while (k2 <= self.N):
# If a right child exists, change the child index to the right child
#if (k2 < self.N) and (self.a[k2] < self.a[k2+1]):
#if (k2 < self.N) and (self.__less(k2, k2+1)):
if (k2 < self.N) and (self._less(k2, k2+1)):
# k2+1 is greater, so use that index for comparison
# i.e, k2+1 is the greater child
k2 += 1
# Exchange if child is greater than parent
#if self.a[k] < self.a[k2]:
#if self.__less(k, k2):
if self._less(k, k2):
#(self.a[k2], self.a[k]) = (self.a[k], self.a[k2])
self.__exchange(k, k2)
k = k2
k2 *= 2
def heapify(self, input_list):
'''
input_list is 0-indexed
internal list self.a is 1-indexed
self.a[1] = first element
self.a[self.N] = last element
'''
self.N = len(input_list)
# Append the input list to [None]
self.a = [None] + input_list
# Sink all elements starting from the end of the second
# to last row
k = self.N / 2
for k in range(k, 0, -1):
self.__sink(k)
def __swim(self, k):
# p = parent index
p = k/2
while p > 0:
# If the parent is less, exchange
#if self.__less(p, k):
if self._less(p, k):
self.__exchange(p, k)
k = p
p = k/2
'''
def __less(self, p, q):
# p and q are heap indexes
return self.keys[self.heap_index[p]] < self.keys[self.heap_index[q]]
'''
# Prevent name-mangling for subclasses
def _less(self, p, q):
'''
p and q are heap indexes
'''
return self.keys[self.heap_index[p]] < self.keys[self.heap_index[q]]
def _less_val(self, value1, value2):
'''
This method is overridden in the "indexed_min_heap" class
'''
return value1 < value2
def __exchange(self, p, q):
'''
p and q are indexes to the heap
'''
#print "exchange(%d, %d)" % (p, q)
(self.heap_index[p], self.heap_index[q]) = (self.heap_index[q], self.heap_index[p])
heap_p = self.heap_index[p]
heap_q = self.heap_index[q]
key_p = self.keys[heap_p]
key_q = self.keys[heap_q]
#print "heap(%d) = %d, key = %d" % (p, heap_p, key_p)
#print "heap(%d) = %d, key = %d" % (q, heap_q, key_q)
self.key_index[key_p] = p
self.key_index[key_q] = q
#self.key_index[self.keys[self.heap_index[p]]] = p
#self.key_index[self.keys[self.heap_index[q]]] = q
def insert(self, key_index, key, value=None):
'''
Add the element to the end and swim
i -> key_index
pq -> self.heap_index
qp -> self.key_index
'''
print "insert(%d, %d)" % (key_index, key)
self.N += 1
self.heap_index.append(key_index)
#while key >= len(self.key_index):
# self.key_index.append(None)
self.key_index[key] = self.N
#while key_index >= len(self.keys):
# self.keys.append(None)
# self.values.append(None)
self.keys[key_index] = key
if value:
self.values[key_index] = value
#for key in self.keys:
# print "key_index[%d] = %d" % (key, self.key_index[key])
self.__swim(self.N)
#self.print_heap()
def remove_max(self):
'''
Element 1 is the max
Exchange with last element
Decrement size
Sink first element
Return tuple of (max_key, value)
'''
#(self.a[self.N], self.a[1]) = (self.a[1], self.a[self.N])
heap_1 = self.heap_index[1]
max_key = self.keys[heap_1]
max_key_index = self.key_index[max_key]
print "remove_max: key[%d] = %d" % (heap_1, max_key)
self.__exchange(1, self.N)
# DEBUGGING
del self.heap_index[self.N]
#del self.keys[heap_1]
#del self.key_index[max_key]
value = None
if heap_1 in self.values:
value = self.values[heap_1]
del self.values[heap_1]
self.N -= 1
self.__sink(1)
return (heap_1, max_key, value)
def remove(self, key_index):
# This check isn't valid for the dictionary version
#if key_index > len(self.keys) or not self.keys[key_index]:
# raise ValueError ("indexed_map_heap.remove error: invalid key_index = %d" % key_index)
if key_index not in self.keys:
raise ValueError ("indexed_map_heap.remove error: invalid key_index = %d" % key_index)
key = self.keys[key_index]
heap_i = self.key_index[key]
k = self.heap_index[self.N]
new_key = self.keys[k]
self.__exchange(heap_i, self.N)
self.N -= 1
#print "remove: after exchange"
#print self.print_heap()
#if new_key < key:
if self._less_val(new_key, key):
self.__sink(heap_i)
print "remove: after sink"
else:
self.__swim(heap_i)
# NEED TO DELETE OLD VALUES FROM DICTIONARIES!!!!
del self.keys[key_index]
del self.key_index[key]
value = self.values.get(key_index, None)
if key_index in self.values:
del self.values[key_index]
# del self.keys[...]
# del self.values[...]
return (key, value)
def change(self, key_index, new_key, new_value=None):
print "change(%d, %d)" % (key_index, new_key)
#if key_index >= len(self.keys):
if key_index not in self.keys:
raise ValueError("indexed_heap.change error: key_index %d is out of range" % key_index)
old_key = self.keys[key_index]
if new_value:
self.values[key_index] = new_value
k = self.key_index[old_key]
self.keys[key_index] = new_key
#if new_key < old_key:
if self._less_val(new_key, old_key):
self.__sink(k)
else:
self.__swim(k)
def contains(self, key_index):
#if key_index < len(self.keys) and self.keys[key_index]:
if key_index in self.keys:
return True
return False
def sort_down(self):
'''
sorts list in place
loop starting at the top index
exchange with last element
sink down top element
'''
n_orig = self.N
for k in range(1, self.N):
# Exchange to place the largest element remaining at the end
#(self.a[1], self.a[self.N]) = (self.a[self.N], self.a[1])
self.__exchange(1, self.N)
# Decrement the length of the remaining elements
self.N -= 1
# Sink the new top element
self.__sink(1)
self.N = n_orig
def print_heap(self):
#print "\nheap N = %d" % self.N
print "\nheap"
k = 1
k2 = 2 * k
# number of characters to print
key_width = 2
min_space = 2
if self.N > 1:
depth = math.floor(math.log(self.N - 1, 2)) + 1
else:
depth = 1
leaves = 2**(depth - 1)
format = "%" + str(key_width) + "d"
# 1 is the spacing between entries on the bottom row
bottom_width = leaves * (min_space + key_width)
indent_width = bottom_width
indent_float = float(bottom_width)
'''
12345678901234567890123457689012
----------------xx indent = 16
--------xx--------------xx indent = 8, spacing = 14
----xx------xx------xx------xx indent = 4, spacing = 6
--xx--xx--xx--xx--xx--xx--xx--xx indent = 2, spacing = 2
'''
while k <= self.N:
row_leaves = 2**(k-1)
row_gap = 2 * (depth - k + 1) - 1
indent_float = indent_float / 2.0
indent_width = int(math.floor(indent_float))
indent = " " * int(indent_width)
spacing = " " * (indent_width * 2 - 2)
if k2 > self.N:
k2 = self.N + 1
pstring = indent
for i in range(k, k2):
heap_i = self.heap_index[i]
key = self.keys[heap_i]
pstring += format % key + spacing
print pstring
k = k2
k2 = 2 * k
print_heap_index = False
if print_heap_index:
print "\ni, heap_index"
for i in range(1, self.N+1):
print "%d, %d" % (i, self.heap_index[i])
print_key_index = False
if print_key_index:
print "key, key_index"
for i in range(0, len(self.keys)):
if self.keys[i]:
key = self.keys[i]
print "[%d] = %d -> %d" % (i, key, self.key_index[key])
def test_indexed_max_heap(test_min_heap = False):
use_random = True
i_remove = 0
if use_random:
N = 31
a = range(1, N+1)
random.shuffle(a)
else:
#a = [3, 5, 6, 4, 1, 7, 2]
old_key = 2
a = [2, 7, 10, 13, 14, 6, 15, 9, 12, 1, 5, 4, 8, 11, 3]
#a = [21, 27, 25, 5, 1, 17, 15, 11, 19, 31, 26, 24, 22, 8, 6, 4, 13, 9, 10, 28, 16, 18, 20, 14, 7, 23, 30, 12, 3, 29, 2]
#old_key = 30
i_remove = a.index(old_key)
print "remove a[%d] = %d" % (i_remove, old_key)
print "input list:"
print repr(a)
if not test_min_heap:
max_h = indexed_max_heap(len(a))
else:
max_h = indexed_min_heap(len(a))
for i in range(0, len(a)):
print "insert a[%d] = %d" % (i, a[i])
max_h.insert(i, a[i])
max_h.print_heap()
#max_h.remove_max()
remove_all = True
if not remove_all:
max_h.remove(i_remove)
max_h.print_heap()
else:
a_copy = list(a)
for i in range(0, len(a)):
j = random.randint(0, len(a_copy) - 1)
key = a_copy.pop(j)
i_remove = a.index(key)
print "\nremove a[%d] = %d" % (i_remove, key)
max_h.remove(i_remove)
max_h.print_heap()
class indexed_min_heap_dict(indexed_max_heap_dict):
def remove_max(self):
raise
def remove_min(self):
return indexed_max_heap_dict.remove_max(self)
def _less(self, p, q):
'''
OPPOSITE comparison for min_heap
p and q are heap indexes
'''
return self.keys[self.heap_index[p]] > self.keys[self.heap_index[q]]
def _less_val(self, value1, value2):
'''
OPPOSITE comparison for min_heap
'''
return value1 > value2
if __name__ == '__main__':
#test_max_heap_1()
#test_max_heap_2()
test_max_heap_3()
#test_indexed_max_heap_3()
#test_indexed_min_heap_3()
#test_indexed_max_heap(True)
#test_min_heap_3()