A Heap is a special Tree-based data structure which is an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node. A common implementation of a heap is the binary heap, in which the tree is a binary tree.

A priority queue is a data structure that stores priorities (comparable values) and perhaps associated information. A priority queue is different from a "normal" queue, because instead of being a "first-in-first-out" data structure, values come out in order by priority. Think of a priority queue as a kind of bag that holds priorities. You can put one in, and you can take out the current highest priority.

A binary heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices: The root element is 0

Left child : (2*i)+1
Right child : (2*i)+2
Parent child : (i-1)/2

A Binary Heap is a Binary Tree with following properties: It’s a complete tree (all levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array. A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary

Tree. Max Binary Heap is similar to MinHeap. 10 10 / \ /
20 100 15 30 / / \ /
30 40 50 100 40

A binary heaps are commonly implemented with an array. Any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be stored compactly. No space is required for pointers; instead, the parent and children of each node can be found by arithmetic on array indices: The root element is 0

Left child : (2*i)+1
Right child : (2*i)+2
Parent child : (i-1)/2

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked lists: In Array:

insert() operation can be implemented by adding an item at end of array in O(1) time.
getMax() operation can be implemented by linearly searching the highest priority item in array. This
operation takes O(n) time.
deleteMax() operation can be implemented by first linearly searching an item, then removing the item by

moving all subsequent items one position back. In a Binary Heap:

getMax() can be implemented in O(1) time,
insert() can be implemented in O(log n) time and
deleteMax() can also be implemented in O(log n) time.

The characteristic of a heap is that it is a structure that maintains data semiordered; thus, it is a good tradeoff between the cost of maintaining a complete order ant the cost of seaching through random chaos. That characteristic is used on many algorithms, such as selection, ordering, or classification. Also consider: Use it whenever you need quick access to the largest (or smallest) item, because that item will always be the first element in the array or at the root of the tree Good for selection algorithms (finding the min or max). A heap allows access to the min or max element in constant time, and other selections (such as median or kth-element) can be done in sub-linear time on data that is in a heap Priority Queue. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods. Anytime when you sort a temporary list, you should consider heaps. Heapsort is one of the best sorting methods being in-place and with no quadratic worst-case scenarios. A heap data structure is useful to merge many already-sorted input streams into a single sorted output stream Graph algorithms. By using heaps as internal traversal data structures, run time will be reduced by polynomial order. Examples of such problems are Prim's minimal spanning tree algorithm and Dijkstra's shortest path problem. Full and almost full binary heaps may be represented in a very space-efficient way using an array alone. The first (or last) element will contain the root. The next two elements of the array contain its children. The next four contain the four children of the two child nodes, etc. Thus the children of the node at position n would be at

positions 2n and 2n+1 in a one-based array, or 2n+1 and 2n+2 in a zero-based array. This allows moving up or down the tree by doing simple index computations. Balancing a heap is done by swapping elements which are out of order. As we can build a heap from an array without requiring extra memory (for the nodes, for example), heapsort can be used to sort an array in-place. One more advantage of heaps over trees in some applications is that construction of heaps can be done in linear time using Tarjan's algorithm.

Priority Queue abstract data type (ADT) can be implemented using other data structures (including Heaps) like: Unordered Array Unordered List Ordered Array Ordered List

Binary Search Tree (BST)
Balanced Binary Search Tree (AVL-tree)
Binary heap

Compare the time efficiency of heap implementation for main operations in Priority Queue ADT with other possible implementations:

----------------------------------------------------------------------------
| Implementation | Insertion | Deletion(DeleteMax/DeleteMin)|Find Max/Min
----------------------------------------------------------------------------
| Unordered Array| 1 | n | n
----------------------------------------------------------------------------
| Unordered List | 1 | n | n
----------------------------------------------------------------------------
| Ordered Array | n | 1 | 1
----------------------------------------------------------------------------
| Ordered List | n | 1 | 1
----------------------------------------------------------------------------
| BST | logn (avg.) | logn (avg.) | logn (avg.)
----------------------------------------------------------------------------

| Balanced BST | log n | log n | log n

----------------------------------------------------------------------------

| Binary Heaps | log n | log n | 1

Heap is generally preferred for priority queue implementation because heaps provide better performance compared arrays or linked lists: In Array:

insert() operation can be implemented by adding an item at end of array in O(1) time.
getMax() operation can be implemented by linearly searching the highest priority item in array. This
operation takes O(n) time.
deleteMax() operation can be implemented by first linearly searching an item, then removing the item by

moving all subsequent items one position back. In a Binary Heap:

getMax() can be implemented in O(1) time,
insert() can be implemented in O(log n) time and
deleteMax() can also be implemented in O(log n) time.

Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum. A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements. So, by taking advantage of this property, we can pop off the max of the heap repeatedly and establish a sorted array. In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i , its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one).

The HeapSort steps are: Create a max heap from the unsorted list Swap the max element, located at the root, with the last element Re- heapify or rebalance the array again to establish the max heap order. The new root is likely not in its correct place. Repeat Steps 2–3 until complete (when the list size is 1) Visualisation: Complexity: Complexity Analysis: Time Complexity: O(n log n) Space Complexity: O(n log n) Best:

O(
n log n)
Average:
O(
n log n)
Worst:
O(
n log n)
Implementation:
JS

var a = [ 9, 10, 2, 1, 5, 4, 3, 6, 8, 7, 13 ];
function swap(a, i, j) {
  var tmp = a[i];
  a[i] = a[j];
  a[j] = tmp;
}
function max_heapify(a, i, length) {
  while (true) {
    var left = i*2 + 1;
    var right = i*2 + 2;
    var largest = i;
    if (left < length && a[left] > a[largest]) {
      largest = left;
    }
  if (right < length && a[right] > a[largest]) {
    largest = right;
  }
if (i == largest) {
  break;
}
swap(a, i, largest);
i = largest;
}
}
function heapify(a, length) {
  for (var i = Math.floor(length/2); i >= 0; i--) {
    max_heapify(a, i, length);
  }
}
function heapsort(a) {
  heapify(a, a.length);
  for (var i = a.length - 1; i > 0; i--) {
    swap(a, i, 0);
    max_heapify(a, 0, i-1);
  }
}
heapsort(a);
PY
def heapsort(lst):
"""

Sorts list in-place with a heap. """

last_element = len(lst) - 1
lst = heapify(lst)
while last_element >= 0:
# swap the max element with the last element
# like popping off the max
swap(lst, 0, last_element)
# rebalance the remaining heap, from index 0 to last_element exclusive
balance(lst, 0, last_element)
last_element -= 1

return lst

def heapify(lst): """ Turns list into a max heap in-place, in linear time. Begins process at 1 depth before leaves. """# initiliazes cur at halfway point based on length of list

if len(lst) % 2 == 0:
cur = len(lst) / 2 - 2
else:
cur = len(lst) / 2 - 1# rebalance until reached beginning of list
while cur >= 0:
balance(lst, cur)
cur -= 1

return lst def swap(lst, i, last_element): """ Swaps two elments of a list - the current and last in this case. """ lst[i], lst[last_element] = lst[last_element], lst[i] def balance(lst, cur, last_element=None): """ Rebalances heap. Keyword arg for last_element allows for re-use in both heapify and heapsort. """ if last_element is None:

last_element = len(lst)
while cur < last_element:
left_child = 2*cur + 1
right_child = 2*cur + 2
# check to see if we're out of bounds for the children
# this is necessary for even length heaps
if left_child >= last_element:

return

if right_child >= last_element:
# since left child is in bounds, check for swap
if lst[cur] < lst[left_child]:
swap(lst, cur, left_child)

return

if we're in bounds for both children, find the max

max_child = find_max_child(lst, left_child, right_child)

check to see if swap needed

if lst[cur] < lst[max_child]:
swap(lst, cur, max_child)
cur = max_child

The major difference between a binary heap and a red-black tree is the performance on certain operations:

Heap Pros It makes an ideal priority queue, since the min/max element (depending on your implementation) is always O(1) access time, so no need to search for it. It's also very fast for insertion of new values - O(1) on average, O(log n) worst case. Heap Cons Slow searches O(n) for random elements. RB Tree Pros Better searching O(log n) and good insertion O(log n) performance. RB Tree Cons Slower min/max searches. More overhead in general.

The brute force solution will be to sort the array in O(n log n) time complexity and take the last 100 numbers but you can do better. You can keep a priority queue (implemented as a heap) of the 100 biggest numbers, iterate through the billion numbers, whenever you encounter a number greater than the smallest number in the queue (the head of the queue), remove the head of the queue and add the new number to the queue. In general, if you need the largest K numbers from a set of N numbers, the complexity is O(N log K) rather than O(N log N) , this can be very significant when K is very small comparing to N . You can also apply problem solving process. Ask interviewer the range or meaning of these numbers to make the problem clear. If, for example, these numbers stands for people's age of within a country (e.g. China), then it's a much easier problem. With a reasonable assumption that nobody alive is older than 200, you can use an int array of size 200 (maybe 201) to count the number of people with the same age in just one iteration. Here the index means the age. After this it's a piece of cake to find 100 largest number. By the way this also is called counting sort. Counting sort takes O(n + k) time and O(n + k) space, where n is the number of items we're sorting and k is the number of possible values.