Last active
December 19, 2015 11:49
-
-
Save landau/5950633 to your computer and use it in GitHub Desktop.
Max Order Priority Queue
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
class MaxPQ(object): | |
def __init__(self): | |
# TODO initialize with array | |
self._N = -1 | |
self._arr = [] | |
pass | |
def _compare(self, a, b): | |
if a > b: return 1 | |
if a < b: return -1 | |
return 0 | |
def _less(self, a, b): | |
# array is zero based, but tree is 1 based | |
# Subtract for real index | |
a -= 1 | |
b -= 1 | |
return self._compare(self._arr[a], self._arr[b]) < 0 | |
def _exch(self, a, b): | |
# array is zero based, but tree is 1 based | |
# Subtract for real index | |
a -= 1 | |
b -= 1 | |
tmp = self._arr[a] | |
self._arr[a] = self._arr[b] | |
self._arr[b] = tmp | |
def is_empty(self): | |
return self._N < 0 | |
def put(self, val): | |
# Add new value to heap | |
self._N += 1 | |
self._arr.append(val) | |
# Restore heap order | |
self._swim(self._N) | |
def _swim(self, child): | |
""" | |
If parent is smaller, exchange positions with child | |
Parent exists at child's position / 2 | |
""" | |
# Tree is 1 based | |
child += 1 | |
# as long as the child isn't root and smaller than | |
# it's parent | |
while child > 1 and self._less(child / 2, child): | |
parent = child / 2 | |
self._exch(parent, child) | |
child = parent | |
# Get max value from heap | |
def del_max(self): | |
# Store value for returning | |
val = self._arr[0] | |
# Switch first item with last | |
# `Exch` expects first item + 1 in PQ | |
# So use 1 instead of 0, N will also be decremented | |
self._exch(1, self._N + 1) | |
# get rid of last element which is our max | |
# from the pq | |
self._arr[self._N] = None | |
self._N -= 1 | |
# Restore heap order | |
self._sink(0) | |
return val | |
def _sink(self, parent): | |
""" | |
if parent becomes smaller than one of the children | |
sink below greater parent until heap order is restored | |
""" | |
parent += 1 | |
# Iterate over 2 * position of element in PQ | |
# until we've reached the length of the PQ | |
while parent * 2 <= self._N: | |
# Level children exist at parent * 2 and parent * 2 + 1 | |
child = parent * 2 | |
# Check if children exists and if right child | |
# is greater than left. If right is larger, inc | |
# parent to position at right child | |
if child < self._N and self._less(child, child + 1): child += 1 | |
# Check if child is greater than parent | |
# If not, we are done | |
if not self._less(parent, child): break | |
# Child is greater, exchange positions | |
self._exch(parent, child) | |
# parent is now in childs position | |
parent = child | |
def __len__(self): | |
# N is zero with 1 value in the PQ | |
# and -1 with no values | |
# so inc my by one :) | |
return self._N + 1 | |
def __str__(self): | |
return "<MaxPQ %d elements>" % len(self) | |
def __repr__(self): | |
return "<MaxPQ %r>" % self._arr | |
@staticmethod | |
def sort(pq): | |
# ensure order | |
N = len(pq) | |
# Start at last level to the right in tree where elements have children | |
k = N / 2 | |
# iterate over all elements in pq to ensure order | |
while k >= 1: | |
MaxPQ.sink(pq, k, N) | |
# Check next element | |
k -= 1 | |
while N > 1: | |
# swap smallest with max | |
MaxPQ.exch(pq, 1, N) | |
# 'remove' element from iteration | |
N -= 1 | |
# Bring smallest back down | |
MaxPQ.sink(pq, 1, N) | |
@staticmethod | |
def sink(pq, parent, N): | |
""" | |
if parent becomes smaller than one of the children | |
sink below greater parent until heap order is restored | |
""" | |
# Iterate over 2 * position of element in PQ | |
# until we've reached the length of the PQ | |
while parent * 2 <= N: | |
# Level children exist at parent * 2 | |
child = parent * 2 | |
# Check if children exists and if right child | |
# is greater than left. If right is larger, inc | |
# parent to position at right child | |
if child < N and MaxPQ.less(pq, child, child + 1): child += 1 | |
# Check if child is greater than parent | |
# If not, we are done | |
if not MaxPQ.less(pq, parent, child): break | |
# Child is greater, exchange positions | |
MaxPQ.exch(pq, child, parent) | |
# parent is now in childs position | |
parent = child | |
@staticmethod | |
def less(pq, a, b): | |
return pq._less(a, b) | |
@staticmethod | |
def exch(pq, a, b): | |
pq._exch(a, b) | |
if __name__ == "__main__": | |
from random import shuffle | |
N = 3 | |
pq = MaxPQ() | |
arr = "abcnsnsdlkjl" | |
for x in arr: pq.put(x) | |
print "%r" % pq | |
#while not pq.is_empty(): | |
# print pq.del_max() | |
MaxPQ.sort(pq) | |
print "Sorted %r" % pq |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment