Created
January 27, 2013 10:01
-
-
Save gnarmis/4647645 to your computer and use it in GitHub Desktop.
min max heap implementation in python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from math import log, floor, pow | |
| class MinMaxHeap(object): | |
| """an implementation of min-max heap using an array, | |
| which starts at 1 (ignores 0th element) | |
| """ | |
| def __init__(self, array=[]): | |
| super(MinMaxHeap, self).__init__() | |
| self.heap = [0] | |
| for i in array: | |
| self.Insert(i) | |
| def Insert(self, value): | |
| """place value at an available leaf, then bubble up from there""" | |
| self.heap = self.heap + [value] | |
| self.BubbleUp(len(self.heap) - 1) | |
| def DeleteAt(self, position): | |
| """delete given position""" | |
| self.heap[position] = self.heap[-1] | |
| del(self.heap[-1]) | |
| self.TrickleDown(position) | |
| def Index(self, value): | |
| return self.heap.index(value) | |
| def PeekMax(self): | |
| if len(self.heap) > 1: | |
| return self.heap[1] | |
| else: | |
| raise Exception | |
| def PeekMin(self): | |
| size = len(self.heap) | |
| if size > 1: | |
| c = [self.heap[1]] | |
| if size >= 2: | |
| c = c + [self.heap[2]] | |
| if size >= 3: | |
| c = c + [self.heap[3]] | |
| return min(c) | |
| else: | |
| raise Exception | |
| def PopMax(self): | |
| m = self.PeekMax() | |
| mi = self.Index(m) | |
| self.DeleteAt(mi) | |
| return m | |
| def PopMin(self): | |
| m = self.PeekMin() | |
| mi = self.Index(m) | |
| self.DeleteAt(mi) | |
| return m | |
| def TrickleDown(self, position): | |
| """delete key at position""" | |
| if self.OnMinLevel(position): | |
| self.TrickleDownMin(position) | |
| else: | |
| self.TrickleDownMax(position) | |
| def TrickleDownMin(self, position): | |
| if self.HasChildren(position): | |
| min_pair = self.SortPairs(self.ChildrenAndGrandChildren(position))[0] | |
| m = min_pair[0] # index of smallest kid | |
| if self.IsGrandChild(position, m): | |
| if self.heap[m] < self.heap[position]: | |
| self.Swap(m, position) | |
| if self.heap[m] > self.heap[self.Parent(m)]: | |
| self.Swap(m, self.Parent(m)) | |
| self.TrickleDownMin(m) | |
| # if not grandchild, m must be a child | |
| else: | |
| if self.heap[m] < self.heap[position]: | |
| self.Swap(m, position) | |
| else: | |
| pass | |
| def TrickleDownMax(self, position): | |
| if self.HasChildren(position): | |
| max_pair = self.SortPairs(self.ChildrenAndGrandChildren(position))[-1] | |
| m = max_pair[0] # index of smallest kid | |
| if self.IsGrandChild(position, m): | |
| if self.heap[m] > self.heap[position]: | |
| self.Swap(m, position) | |
| if self.heap[m] < self.heap[self.Parent(m)]: | |
| self.Swap(m, self.Parent(m)) | |
| self.TrickleDownMax(m) | |
| # if not grandchild, m must be a child | |
| else: | |
| if self.heap[m] > self.heap[position]: | |
| self.Swap(m, position) | |
| else: | |
| pass | |
| def BubbleUp(self, position): | |
| if self.OnMinLevel(position): | |
| if self.HasParent(position): | |
| if self.heap[position] > self.heap[self.Parent(position)]: | |
| self.Swap(position, self.Parent(position)) | |
| self.BubbleUpMax(self.Parent(position)) | |
| else: | |
| self.BubbleUpMin(position) | |
| else: | |
| if self.HasParent(position): | |
| if self.heap[position] < self.heap[self.Parent(position)]: | |
| self.Swap(position, self.Parent(position)) | |
| self.BubbleUpMin(self.Parent(position)) | |
| else: | |
| self.BubbleUpMax(position) | |
| def BubbleUpMin(self, position): | |
| grandparent = self.Parent(self.Parent(position)) | |
| if self.HasGrandParent(position): | |
| if self.heap[position] < self.heap[grandparent]: | |
| self.Swap(position, grandparent) | |
| self.BubbleUpMin(grandparent) | |
| def BubbleUpMax(self, position): | |
| if self.HasGrandParent(position): | |
| grandparent = self.Parent(self.Parent(position)) | |
| if self.heap[position] > self.heap[grandparent]: | |
| self.Swap(position, grandparent) | |
| self.BubbleUpMax(grandparent) | |
| def Swap(self, a, b): | |
| """swap values between a and b""" | |
| a_val = self.heap[a] | |
| b_val = self.heap[b] | |
| self.heap[a] = b_val | |
| self.heap[b] = a_val | |
| def Parent(self, child): | |
| """return child's parent""" | |
| return int(child) / 2 | |
| def IsGrandChild(self, parent, grand_child): | |
| """tell whether grand_child is parent's grandchild or not""" | |
| if self.HasGrandChildren(parent): | |
| size = len(self.heap) | |
| if grand_child < size: | |
| return True | |
| else: | |
| return False | |
| else: | |
| return False | |
| def SortPairs(self, list_of_pairs): | |
| """return 2-tuple representing smallest, sorted by value in second""" | |
| return sorted(list_of_pairs, key=lambda tup: tup[1]) | |
| def ChildrenAndGrandChildren(self, position): | |
| """ | |
| return list of children's and grandchildren's indices | |
| Don't call if position doesn't have children! | |
| """ | |
| if self.HasChildren(position): | |
| a = [] | |
| a = a + [(int(pow(2, position)), self.heap[int(pow(2, position))])] | |
| a = a + [(int(pow(2, position)) + 1, self.heap[int(pow(2, position)) + 1])] | |
| if self.HasChildren(int(pow(2, position))): | |
| cpos = int(pow(2, position)) | |
| a = a + [(int(pow(2, cpos)), self.heap[int(pow(2, cpos))])] | |
| a = a + [(int(pow(2, cpos)) + 1, self.heap[int(pow(2, cpos)) + 1])] | |
| if self.HasChildren(int(pow(2, position)) + 1): | |
| cpos = int(pow(2, position)) + 1 | |
| a = a + [(int(pow(2, cpos)), self.heap[int(pow(2, cpos))])] | |
| a = a + [(int(pow(2, cpos)) + 1, self.heap[int(pow(2, cpos)) + 1])] | |
| return a | |
| else: | |
| raise Exception | |
| def HasParent(self, position): | |
| p = self.Parent(position) | |
| if p is not 0: | |
| return True | |
| else: | |
| return False | |
| def HasGrandParent(self, position): | |
| gp = self.Parent(self.Parent(position)) | |
| if gp is not 0: | |
| return True | |
| else: | |
| return False | |
| def HasChildren(self, position): | |
| """check if 2^position and 2^(position)+1 exist""" | |
| size = len(self.heap) | |
| if (pow(2, position) < size) or ((pow(2, position) + 1) < size): | |
| return True | |
| else: | |
| return False | |
| def HasGrandChildren(self, position): | |
| """check if either of position's children have children of their own""" | |
| if self.HasChildren(int(pow(2, position))) or \ | |
| self.HasChildren(int(pow(2, position)) + 1): | |
| return True | |
| else: | |
| return False | |
| def OnMinLevel(self, position): | |
| """returns bool - is it on a min level?""" | |
| test = self.OnLevel(position) % 2 | |
| if test == 0: | |
| return False | |
| else: | |
| return True | |
| def OnMaxLevel(self, position): | |
| """returns bool - is it on a max level?""" | |
| test = self.OnLevel(position) % 2 | |
| if test == 0: | |
| return True | |
| else: | |
| return False | |
| def OnLevel(self, position): | |
| """returns what level the key at position is on""" | |
| return floor(log(int(position), 2)) |
The DeleteAt does NOT work in all operations. For example, suppose we have the following min-max heap:
level 0 10
level 1 92 56
level 2 41 54 23 11
level 3 69 51 55 65 37 31
Now apply your DeleteAt algorithm to delete 55. You replace 55 with 31. You delete 55, and you obtain this:
level 0 10
level 1 92 56
level 2 41 54 23 11
level 3 69 51 31 65 37
Now you TricleDown start from 31. TricleDown checks if we're in an even or odd level: we're in an odd level (3), so TricleDown calls TrickleDownMax starting from 31, but since 31 has no children, it stops. But if you observe that leaves the data structure in a state that is no more a min-max heap, because 54, which is at even level and therefore should be smaller than its descendants, is greater than 31, one of its descendants.
This is a max-min heap actually.
heap = MinMaxHeap()
# ignores 0th element as he stated
print heap.OnMinLevel(1)
# FalseSome modifications to make it a min-max heap:
def OnMinLevel(self, position):
"""returns bool - is it on a min level?"""
test = 1- self.OnLevel(position) % 2 # => inverse
if test == 0:
return False
else:
return True
def OnMaxLevel(self, position):
"""returns bool - is it on a max level?"""
test = 1- self.OnLevel(position) % 2 # => inverse
if test == 0:
return True
else:
return False
initialization is not efficient, could heapify the data, not insert one by one
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This code will generate an error if the node does not have right child/grandchild. The hasChildren method returns true even if a node has only 1 child, but the calling function (Children and GrandChildren) then attempts to access both left and right child.