In [ ]:
%%HTML
<style>
.container { width:100% }
</style>
In [ ]:
import graphviz as gv
The function toDot takes four arguments:
A is an array of natural numbers of length $n$,f is a natural number such that $0 \leq f < n$ holds,g is a natural number such that $f < g < n$ holds,u is a natural number such that $0 \leq u < n$ holds.
This argument is optional.The function returns a graphical representation of the array A as a heap.
This graphical representation is stored as a directed graph with an encoding suitable for graphviz.
The part A[0:g] is represented as a binary tree, while the part A[g:] is represented
as a list. Furthermore, all indexes in the range A[k:g] satisfy the heap condition. The nodes in the range [0:k-1]
are colored red. If u is set, the node A[u] is colored orange.
In [ ]:
def heapToDot(A):
n = len(A)
dot = gv.Digraph(node_attr={'shape': 'record'})
for k, (p, o) in enumerate(A):
if str(p) != str(o):
dot.node(str(k), label='{' + str(p) + '|' + str(o) + '|' + str(o.mIndex) + '|' + str(k) + '}', style='rounded')
else:
dot.node(str(k), label='{' + str(p) + '|' + str(k) + '}', style='rounded')
for k in range(0, n // 2):
if 2 * k + 1 < n:
dot.edge(str(k), str(2 * k + 1))
if 2 * k + 2 < n:
dot.edge(str(k), str(2 * k + 2))
return dot
The function call swap(A, i, j) takes an array A and two indexes i and j and exchanges the elements at these indexes.
In [ ]:
def swap(A, i, j):
pi, oi = A[i]
pj, oj = A[j]
oi.mIndex = j
oj.mIndex = i
A[i] = pj, oj
A[j] = pi, oi
The function ascend takes two arguments:
A is an array that is represented as a list in Python.k is an index into the array A.
Therefore we have $k \in \bigl\{0, \cdots, \texttt{len}(A)-1\bigr\}$.
The array A represents a heap. However, the heap condition might be violated
at index k: It might be the case that the element at this index is to small and needs to rise to the top
of the heap. The function ascend will fix the heap condition and will rise the element A[k] as much
as is necessary to turn A into a heap.
In [ ]:
def ascend(A, k):
while k > 0:
p = (k - 1) // 2
if A[k] < A[p]:
swap(A, p, k)
k = p
else:
return k
return 0
The function descend(A) takes one argument A where A is an array that is organized as a heap.
but possibly has its heap condition violated at its root, i.e. at index 0. The
purpose of the procedure descend is to restore the heap condition at the root.
We initialize a variable k as 0 and the while-loop proceeds as follows:
j of the left subtree below index k.We check whether there also is a right subtree at position j+1.
This is the case if j + 1 <= n where n = len(A) - 1.
k, we exchange the element at position k
with the child that has the higher priority, i.e. the child that is smaller. Next, we check in line 9 whether the heap condition is violated at index k.
If the heap condition is satisfied, there is nothing left to do and the procedure returns.
Otherwise, the element at position k is swapped with
the element at position j.
Of course, after this swap it is possible that the heap condition is
violated at position j. Therefore, k is set to j and the while-loop continues
as long as the node at position k has at least one child, i.e. as long as
2 * k + 1 <= n.
In [ ]:
def descend(A):
n = len(A) - 1
k = 0
while 2 * k + 1 <= n:
j = 2 * k + 1
if j + 1 <= n and A[j] > A[j + 1]:
j += 1
if A[k] < A[j]:
return
swap(A, k, j)
k = j
The function insert(H, x) takes two arguments:
H is a heap that is represented as an array.x is a pair of the form (p, o) wherep is a natural number interpreted as a priority. The smaller the number, the higher the priority.o is an object. This method inserts the pair x into the heap H. Furthermore, the object o is modified so that it remembers
the index at which it is stored in H. This is done by storing this index in o.mIndex.
In [ ]:
def insert(H, x):
n = len(H)
H.append(x)
_, o = x
o.mIndex = n
k = ascend(H, n)
o.mIndex = k
The function elevate(H, o, p) takes three arguments.
H is a list that is organized as a heap.o is an object that occurs in the heap H at index o.mIndex, i.e. we have H[o.mIndex] = p_old, o.mIndex,
where p_old is the priority that was used when o was stored in H.p is the new priority of o in H. This priority must be higher than the priority p_old, i.e. we must have p < p_old.The function call elevate(H, o, p) elevates the priority of the object o to p in H and takes care that o is stored further up in H
so that the heap property of H is maintained.
In [ ]:
def elevate(H, o, p):
k = o.mIndex
H[k] = (p, o)
ascend(H, k)
In [ ]:
def remove(H):
pFirst, oFirst = H[0]
pLast , oLast = H[-1]
oLast.mIndex = 0
H[0] = pLast, oLast
H.pop(-1)
descend(H)
return pFirst, oFirst
In [ ]:
class Node:
def __init__(self, value):
self.mValue = value
def __hash__(self):
return hash(self.mValue)
def __repr__(self):
try:
return 'Node(' + str(self.mValue) + ':' + str(self.mIndex) + ')'
except AttributeError:
return 'Node(' + str(self.mValue) + ')'
def __str__(self):
return str(self.mValue)
def __eq__(self, other):
if other == None:
return False
return self.mValue == other.mValue
def __lt__(self, other):
return self.mValue < other.mValue
In [ ]:
import string
In [ ]:
def demo1():
L = [ (i, Node(c)) for i, c in enumerate(string.ascii_lowercase) ]
_, w = L[22]
H = []
for i, x in enumerate(L):
insert(H, x)
display(heapToDot(H))
print('Elevating "w" to priority 2:')
elevate(H, w, 2)
display(heapToDot(H))
In [ ]:
demo1()
In [ ]:
import random as rnd
In [ ]:
def heap_sort(L):
H = []
for x in L:
insert(H, x)
display(heapToDot(H))
S = []
while H != []:
p, _ = remove(H)
display(heapToDot(H))
S.append(p)
return S
In [ ]:
def demo2():
L = [ rnd.randrange(1, 200) for n in range(12) ]
L = [ (n, Node(n)) for n in L ]
print("L = ", L)
S = heap_sort(L)
print("S = ", S)
In [ ]:
demo2()
In [ ]: