Basic Examples¶

Aheapsort can be implemented bypushing all values onto a heap and then popping off the smallest values one at atime:

>>>defheapsort(iterable):...h=[]...forvalueiniterable:...heappush(h,value)...return[heappop(h)foriinrange(len(h))]...>>>heapsort([1,3,5,7,9,2,4,6,8,0])[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

This is similar tosorted(iterable), but unlikesorted(), thisimplementation is not stable.

Heap elements can be tuples. This is useful for assigning comparison values(such as task priorities) alongside the main record being tracked:

>>>h=[]>>>heappush(h,(5,'write code'))>>>heappush(h,(7,'release product'))>>>heappush(h,(1,'write spec'))>>>heappush(h,(3,'create tests'))>>>heappop(h)(1, 'write spec')

Priority Queue Implementation Notes¶

Apriority queue is common usefor a heap, and it presents several implementation challenges:

• Sort stability: how do you get two tasks with equal priorities to be returnedin the order they were originally added?

• Tuple comparison breaks for (priority, task) pairs if the priorities are equaland the tasks do not have a default comparison order.

• If the priority of a task changes, how do you move it to a new position inthe heap?

• Or if a pending task needs to be deleted, how do you find it and remove itfrom the queue?

A solution to the first two challenges is to store entries as 3-element listincluding the priority, an entry count, and the task. The entry count serves asa tie-breaker so that two tasks with the same priority are returned in the orderthey were added. And since no two entry counts are the same, the tuplecomparison will never attempt to directly compare two tasks.

Another solution to the problem of non-comparable tasks is to create a wrapperclass that ignores the task item and only compares the priority field:

fromdataclassesimportdataclass,fieldfromtypingimportAny@dataclass(order=True)classPrioritizedItem:priority:intitem:Any=field(compare=False)

The remaining challenges revolve around finding a pending task and makingchanges to its priority or removing it entirely. Finding a task can be donewith a dictionary pointing to an entry in the queue.

Removing the entry or changing its priority is more difficult because it wouldbreak the heap structure invariants. So, a possible solution is to mark theentry as removed and add a new entry with the revised priority:

pq=[]# list of entries arranged in a heapentry_finder={}# mapping of tasks to entriesREMOVED='<removed-task>'# placeholder for a removed taskcounter=itertools.count()# unique sequence countdefadd_task(task,priority=0):'Add a new task or update the priority of an existing task'iftaskinentry_finder:remove_task(task)count=next(counter)entry=[priority,count,task]entry_finder[task]=entryheappush(pq,entry)defremove_task(task):'Mark an existing task as REMOVED.  Raise KeyError if not found.'entry=entry_finder.pop(task)entry[-1]=REMOVEDdefpop_task():'Remove and return the lowest priority task. Raise KeyError if empty.'whilepq:priority,count,task=heappop(pq)iftaskisnotREMOVED:delentry_finder[task]returntaskraiseKeyError('pop from an empty priority queue')

Theory¶

Heaps are arrays for whicha[k]<=a[2*k+1] anda[k]<=a[2*k+2] for allk, counting elements from 0. For the sake of comparison, non-existingelements are considered to be infinite. The interesting property of a heap isthata[0] is always its smallest element.

The strange invariant above is meant to be an efficient memory representationfor a tournament. The numbers below arek, nota[k]:

0123456789101112131415161718192021222324252627282930

In the tree above, each cellk is topping2*k+1 and2*k+2. In a usualbinary tournament we see in sports, each cell is the winner over the two cellsit tops, and we can trace the winner down the tree to see all opponents s/hehad. However, in many computer applications of such tournaments, we do not needto trace the history of a winner. To be more memory efficient, when a winner ispromoted, we try to replace it by something else at a lower level, and the rulebecomes that a cell and the two cells it tops contain three different items, butthe top cell «wins» over the two topped cells.

If this heap invariant is protected at all time, index 0 is clearly the overallwinner. The simplest algorithmic way to remove it and find the «next» winner isto move some loser (let’s say cell 30 in the diagram above) into the 0 position,and then percolate this new 0 down the tree, exchanging values, until theinvariant is re-established. This is clearly logarithmic on the total number ofitems in the tree. By iterating over all items, you get anO(n logn) sort.

A nice feature of this sort is that you can efficiently insert new items whilethe sort is going on, provided that the inserted items are not «better» than thelast 0’th element you extracted. This is especially useful in simulationcontexts, where the tree holds all incoming events, and the «win» conditionmeans the smallest scheduled time. When an event schedules other events forexecution, they are scheduled into the future, so they can easily go into theheap. So, a heap is a good structure for implementing schedulers (this is whatI used for my MIDI sequencer :-).

Various structures for implementing schedulers have been extensively studied,and heaps are good for this, as they are reasonably speedy, the speed is almostconstant, and the worst case is not much different than the average case.However, there are other representations which are more efficient overall, yetthe worst cases might be terrible.

Heaps are also very useful in big disk sorts. You most probably all know that abig sort implies producing «runs» (which are pre-sorted sequences, whose size isusually related to the amount of CPU memory), followed by a merging passes forthese runs, which merging is often very cleverly organised[1]. It is veryimportant that the initial sort produces the longest runs possible. Tournamentsare a good way to achieve that. If, using all the memory available to hold atournament, you replace and percolate items that happen to fit the current run,you’ll produce runs which are twice the size of the memory for random input, andmuch better for input fuzzily ordered.

Moreover, if you output the 0’th item on disk and get an input which may not fitin the current tournament (because the value «wins» over the last output value),it cannot fit in the heap, so the size of the heap decreases. The freed memorycould be cleverly reused immediately for progressively building a second heap,which grows at exactly the same rate the first heap is melting. When the firstheap completely vanishes, you switch heaps and start a new run. Clever andquite effective!

In a word, heaps are useful memory structures to know. I use them in a fewapplications, and I think it is good to keep a “heap” module around. :-)

Footnotes

The disk balancing algorithms which are current, nowadays, are more annoyingthan clever, and this is a consequence of the seeking capabilities of the disks.On devices which cannot seek, like big tape drives, the story was quitedifferent, and one had to be very clever to ensure (far in advance) that eachtape movement will be the most effective possible (that is, will bestparticipate at «progressing» the merge). Some tapes were even able to readbackwards, and this was also used to avoid the rewinding time. Believe me, realgood tape sorts were quite spectacular to watch! From all times, sorting hasalways been a Great Art! :-)