Another way to implement a priority queue is to use a heap. You have seen how to build a heap efficiently so that storage is minimal, heap creation takes at most O(n) time, and reheaping takes at most O(lg n) time. To use a heap for the priority queue, the records are stored at the nodes of a heap that is ordered by priority field values. To insert a new record, place it as a new rightmost entry at the greatest depth of the heap. Then let it work its way up in the heap as in the first heap creation algorithm. Adding the new record in this way will take time at most O(lg n). To delete a record, simply delete the record at the root of the heap, and then reheap by invoking shift. This takes time at most O(lg n). The time to create the heap initially will be at most O(n) if the second heap creation algorithm is used. This is also the time that would be required to create an initial unordered array or unordered list of records. To create sorted arrays or lists takes time at most O(n lg n). Referring to Table 9.1, you can see that the heap implementation affords a compromise solution. With arrays and lists, one operation can be done quickly (in constant time) and the other in O(n) time. With the heap, both operations can be done in at most O(lg n) time.