Sunday, December 14, 2014

PriorityQueue and binary heap

I decided to take a close look of this when I try to solve Merge k Sorted Lists.

In a nutshell, priority queue is based on heap. The elements of the queue are ordered in their natural ordering, or by a Comparator provided at queue construction time. It doesn't permit null elements nor as non-comparable objects. Because it is based on a heap, the enqueing and dequeing methods (offer, poll, remove(), and add) has O(log(n)) complexity. The remove(object) and contains(Object) has linear complexity. It provides constant time for the retrieval methods (peek, element, and size)

A binary heap is a complete binary tree that each level, except possibly the bottom most level, is completely filled. Height of the tree is log(n).
A MinHeap: for every node x, parent(x).val < x.val;
A MaxHeap: parent(x).val > x.val
Duplicates are allowed.


Implementation of complete binary tree as array: 
Given element at position i in the array: 
Left child(i) = at position 2i
Right child(i) = at position 2i + 1
Parent(i) = at position floor(i/2)

Just for my curiosity:
The offer method inserts and element if possible, otherwise returning false. This differs from the Collection.add method, which can fail to add an element only by throwing an unchecked exception. The offer method is designed for use when failure is a normal, rather than exceptional occurrence. e.g., in fixed-capacity (or "bounded") queues.


No comments:

Post a Comment