Skip to content

1. PriorityQueue vs. TreeSet TreeMap

Jump to bottom
Xin Wan edited this page Jul 8, 2018 · 1 revision

PriorityQueue

Heap

  • The root of the tree is at index 0.
  • left child of index i = 2 * i + 1
  • right child of index i = 2 * i + 2
  • parent of index i = (i - 1) / 2

Basic Heap Internal Operations

  1. percolateUp()
  • when to use? -> the element need to be moved up. For example, when offering a new element into the heap.
  • how? -> compare the element with its parent, move it up when necessary. Do this until the element does not need to be moved.
  1. percolateDown()
  • when to use? -> The element need to be moved down to maintain the heap's property. For example, when poll the root element from the heap
  • how? move the last element to the top position. compare the element with its two children. swap with the smallest child.
  1. Heapify()
  • Convert an array into a heap in O(n) time by using percolateDown. (If using percolateUp, it will take O(nlogn))
  • how? -> For each node that has at least one child, we perform percolateDown() action, in this order of from the nodes on the deepest level to the root.

Key points

  • percolateUp(int index): 1. offer(), 2. update()
  • percolateDown(int index): 1. poll() 2. update() 3. heapify()

经典问题

  • Top k, k smallest

  • find median

  • BFS2

  • heapify: O(n) convert an arbitary array to its PriorityQueue representation. (percolateUp, percolateDown)

  • The prerequisite of O(logn) for update() is the position(index) must be known

Possible solutions to make update(value) / remove(value) more efficient

  • Lazy deletion: mark the value as delete but not really remove it. remove it only when it is at the top of the heap.
  • Maintain the mapping of the value with its position(index). HashMap (This will be powerful, but hard to implement (need to implement all internal operations of the PriorityQueue))
  • Use "TreeSet/TreeMap"

Difference between PriorityQueue and Balanced BST (TreeMap, TreeSet)

                       PriorityQueue             TreeMap, TreeSet
getMax/Min                O(1)                        O(logn)
Search                    O(n)                        O(logn)
Conducting the sorted seq O(nlogn)                    O(n)
floor(largest smaller)    O(n)                        O(logn)
ceiling(smallest larger)  O(n)                        O(logn)
Range View                O(n)                        O(logn + k) - k is the number of elements in the range.

TreeMap API

ceilingEntry(K key)
ceilingKey(K key)
floorEntry(K key)
floorKey(K key)
firstEntry()
firstKey()
lastEntry()
lastKey()
pollFirstEntry()
pollLastEntry()
subMap(K fromeKey, boolean fromInclusive, K toKey, boolean toInclusive)
headMap(K toKey)
headMap(K toKey, boolean inclusive)
tailMap(K fromKey)
tailMap(K fromKey, boolean inclusive)

TreeSet API

first()
floor(E e)
ceiling(E e)
last()
pollFirst()
pollLast()
subSet(K fromeKey, boolean fromInclusive, K toKey, boolean toInclusive)
headSet(E toElement)
headSet(E toElement, boolean inclusive)
SortedSet<E> tailSet(E fromElement)
SortedSet<E> tailSet(E fromElement, boolean inclusive)

The benefit of PriorityQueue

  • getMax in maxHeap or getMin in minHeap is O(1)

The benefits of TreeMap/TreeSet(BBST):

  • update /delete value is O(logn)
  • we can achieve at the same time, get max and get min are all O(logn)
  • floor()/ ceiling() is O(logn)
  • lookup is O(logn)
  • sorted sequenced view / range view is much more efficient (eg: for subnet with range view in [x, y], you can use iterator to achieve amortized O(1) next())

Top K problems - Top K smallest / largest

  1. k-th smallest/largest element in unsorted array
  2. k smallest/largest elements in unsorted array
  3. The k closest points in 3D space to point of (0, 0, 0) - distance to (0, 0, 0)
  4. k sorted array/list, pick one element from each of them, what is the smallest range, the range is defined as the difference between the largest one and the smallest one?
{1, 5, 1}
{2, 4, 20}
{6, 15}
Solution [5, 4, 6]
  1. K-diff sorted array (each of the element has at most k as distance to its sorted position), how to sort it efficiently? < O(nlogn)
Example:
A = {3, 2, 1, 5, 4, 6} k = 2


time O(nlogK)

Clone this wiki locally