
Data Structure: Max Priority Queue
Today I will implement another important abstract data type – priority queue. Priority queues are used:
 in heap sort
 to track top N elements in a very long sequence
 to merge K ordered sequences and produce single ordered sequence
Usually priority queues have following functions:
 insert() – to add new item with a priority
 deleteMin() or deleteMax() – to remove an item with min/max priority
 findMin() or findMax() – to get an item with min/max priority
 length() – to get the number of items in the priority queue
As a foundation I’ll use in the last post described efficient data structure – binary heap (in fact, maxheap). Overall, priority queue can be seen as a generalization of stack and queue data structures. Stack can be implemented as a max priority queue where priority of each inserted element is monotonically increasing and queue – where priority of each inserted element is monotonically decreasing.
The implementation of max priority queue (tests) is almost identical to the maxheap implementation:
Complexity:
 insert  O(logn)
 deleteMin/deleteMax  O(logn)
 findMin/findMax  O(1)

Data Structure: Binary Heap
Today I will implement very efficient data structure – binary heap. Binary heap – is an arraybased complete binary tree (binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible) which satisfies one of the following ordering properties:
 minheap – the value of each node is not smaller than value of its parent with smallest element at the root;
 maxheap – the value of each node is not bigger than value of its parent with biggest element at the root Binary heap is a foundation for an abstract data type  priority queue, wich I will cover in next post.
Due to the nature of binary heap (complete binary tree) it can be very efficiently implemented using dynamic array. Items in the array are usually stored starting from index 1, thus allowing very easy navigation through binary heap:
 for the item with index k its parent index is k >> 1
 for the item with index k children indexes are k << 1 and k << 1 + 1
Usually binary heaps have following functions:
 insert() – to add new item
 delete() – to remove min or max item (depending on the ordering)
 length() – to get the number of items in binary heap
To add new item:
 add the item to the bottom level of the binary heap (as the last possible item)
 compare added item with its parent
 if they are in correct order – break
 else – exchange items and repeat with the parent
To delete maximum item (for maxheap) or minimum item (for minheap):
 replace the root of the binary heap with the last item on the bottom level
 compare new root with the biggest (for maxheap) or smallest (for minheap) of children
 if they are in correct order – break
 else – exchange items and repeat with the selected child
Bellow you can find possible implementation of the binary heap (tests):
Complexity:
 insert  O(logn)
 delete  O(logn)

Presentation: Continuous Happiness by Continuous Delivery
Recently at Build Stuff conference I gave a practical talk on Continuous Delivery. Enjoy and tell what you think!