|
Resident Grouch
Join Date: Jun 2005
Posts: 6,453
Rep Power: 10 
|
This is a heapsort. Rather than just pluck a function from the library and inexplicably illustrate the sort, I have implemented the sort. This approach uses an array representation for the tree. There are interesting things about the heapsort which aren't illustrated here, such as sorting in-place and the implications that has on the min/max nature of the heap. Google will be more than happy to satisfy your curiosity.
A heap may be either a min heap or a max heap. The requirements for a heap are that every parent is less (greater) than its children. The tree must also be complete; that is, every level is filled with the possible exception of the last, which is packed to the "left". The sort is accomplished by plucking out the root and placing it in the output list. It is then replaced by the most extreme element, which almost certainly breaks the heapness. The tree is then re-heaped and it's all done again. Obviously, the tree shrinks as the sort progresses. This storage may be used to accomplish the (quasi) in-place sort mentioned above. In re-heaping, one finds that only half the tree needs to be adjusted. Moving into this half, one finds that only half of the sub-hive needs to be adjusted. This is the "divide and conquer" approach that also makes sorts like quicksort effective.
As for time complexity, forming a heap from a wild tree requires, worst case, 3N comparisons. The sort, which requires re-heaping (quicker than the heapify), needs, worst case, Nlog(N) comparisons.
class Heap:
def __init__ (I, theHeap = [], desc = False):
'''
Initializes a newly instantiated heap. If data is passed
in the tree will be heapified on construction.
'''
I.theHeap = theHeap
I.nGoodies = len (theHeap)
I.desc = desc
if I.nGoodies > 0: I.heapify ()
def theWinnah (I, a, b):
'''
Comparison function that adapts to whether or not the sort
is ascending or descending.
'''
if I.desc == False: return (a < b)
else: return (b <= a)
def showHive (I):
'''
Arrange the tree in a visual hive. The tree must have sixteen
or fewer members.
'''
if I.nGoodies > 16:
print "Hive too large to show"
return
i = 0
level = 0
lineLength = 80
while i < I.nGoodies:
pcount = 2**level
cellWidth = lineLength / pcount
line = ""
while pcount > 0:
word = I.theHeap [i]
line += word.center (cellWidth, ' ')
pcount -= 1
i += 1
if i >= I.nGoodies: break
print line
level += 1
def heapify (I, iParent = 0):
'''
This adjusts the tree so that it qualifies as a heap. That is,
it is a complete tree and any parent is smaller (larger, for
descending sorts) than either of its children. This is not as
efficient as the reheap process, because the entire tree must
be examined.
'''
if I.iLeft (iParent) < I.nGoodies:
# Left child exists
if I.iLeft (I.iLeft (iParent)) < I.nGoodies:
# And has a child
I.heapify (I.iLeft (iParent))
if I.theWinnah (I.theHeap [I.iLeft (iParent)].lower (),
I.theHeap [iParent].lower ()):
# Left child less (greater) than parent,
# swap and reaheapify the hive
I.swap (iParent, I.iLeft (iParent))
I.heapify (I.iLeft (iParent))
#I.heapify (iParent)
if I.iRight (iParent) < I.nGoodies:
# Right child exists
if I.iRight (I.iRight (iParent)) < I.nGoodies:
# And has a child
#print I.theHeap [I.iRight (iParent)], I.iRight (iParent)
I.heapify (I.iRight (iParent))
if I.theWinnah (I.theHeap [I.iRight (iParent)].lower (),
I.theHeap [iParent].lower ()):
# Right child less (greater) than parent
I.swap (iParent, I.iRight (iParent))
I.heapify (I.iRight (iParent))
#I.heapify (iParent)
def reHeap (I, iParent = 0):
'''
Reheaps the tree after the root is removed and replaced by the
most extreme (positionally) value. Beginning at the root, only
one of the child hives needs to be adjusted. When the child hive
is adjusted, only one of its child hives has to be adjusted. This
divide and conquer approach is where the efficiency arises.
'''
if I.iLeft (iParent) < I.nGoodies:
# Left child exists
if I.theWinnah (I.theHeap [I.iLeft (iParent)].lower (),
I.theHeap [iParent].lower ()):
# Not a heap, left child greater (smaller) than parent
if I.iRight (iParent) < I.nGoodies \
and\
I.theWinnah (I.theHeap [I.iRight (iParent)].lower (),
I.theHeap [I.iLeft (iParent)].lower ()):
# Right child lesser (greater) of the three
I.swap (iParent, I.iRight (iParent))
I.reHeap (I.iRight (iParent))
else:
# Left child lesser (greater) of the three
I.swap (iParent, I.iLeft (iParent))
I.reHeap (I.iLeft (iParent))
elif I.iRight (iParent) < I.nGoodies \
and\
I.theWinnah (I.theHeap [I.iRight (iParent)].lower (),
I.theHeap [iParent].lower ()):
# Not a heap, right child less (greater) than parent
I.swap (iParent, I.iRight (iParent))
I.reHeap (I.iRight (iParent))
def iLeft (I, iParent): return 2 * iParent + 1
def iRight (I, iParent): return 2 * iParent + 2
def swap (I, srcIndex, dstIndex):
'''
Exchanges the two values at the specified indexes.
'''
temp = I.theHeap [srcIndex]
I.theHeap [srcIndex] = I.theHeap [dstIndex]
I.theHeap [dstIndex] = temp
def sort (I):
'''
Sorts the heap by removing the root (the most extreme value)
to the output list and replacing the root with the value at
the most extreme position.
'''
unsorted = Heap (I.theHeap [:], I.desc)
sorted = []
while unsorted.nGoodies > 0:
sorted.append (unsorted.theHeap [0])
unsorted.nGoodies -= 1
unsorted.theHeap [0] = unsorted.theHeap [unsorted.nGoodies]
unsorted.reHeap ()
I.theHeap = sorted [:]
def main():
''' Illustrate a heapsort. If a list is passed in,
it is heapified on construction.'''
theThangs = ["This", "is", "an", "illustration",
"of", "a", "heapsort. ",
"Its", "time", "complexity", "is",
"usually", "expressed", "as", "O(blah)"]
print "The stuff: ",
for i in theThangs: print i,
print
heap = Heap (theThangs)
print "\nHeapified on construction: "
heap.showHive ()
heap.sort ()
print
print "Sorted (ascending): ",
for i in heap.theHeap: print i,
print
print
print "Set mode to descending"
heap.desc = True;
heap.heapify ()
print "Heapified: "
heap.showHive ()
heap.sort ()
print
print "Sorted (descending): ",
for i in heap.theHeap: print i,
print
raw_input ("\nPress ENTER to exit: ")
if __name__ == '__main__':
main()
Quote:
|
Originally Posted by Output
The stuff: This is an illustration of a heapsort. Its time complexity is usually ex
pressed as O(blah)
Heapified on construction:
a
illustration an
Its is complexity as
This time of is usually expressed heapsort. O(blah)
Sorted (ascending): a an as complexity expressed heapsort. illustration is is Its O
(blah) of This time usually
Set mode to descending
Heapified:
usually
Its time
complexity is O(blah) This
a an expressed is as heapsort. illustration of
Sorted (descending): usually time This of O(blah) Its is is illustration heapsort.
expressed complexity as an a
Press ENTER to exit: |
|