binary heap

• GRE Computer Science Question 02

http://www.youtube.com/watch?v=Imfaj84IaWY&feature=relmfu

• Heaps

http://www.youtube.com/watch?v=_9QXNFcrF4c

• Heaps Part 2

http://www.youtube.com/watch?v=DHhPg01rBGs&feature=relmfu

• Binary Heaps

A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:

the min-heap property: the value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
the max-heap property: the value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.

Since a heap is a complete binary tree, it has a smallest possible height - a heap with N nodes always has O(log N) height.

http://www.cs.cmu.edu/~adamchik/15-121/lectures/Binary%20Heaps/heaps.html

• Binary Heaps

A binary heap is a complete binary tree, where each node has a higher priority than its children

Complete binary tree: Each node has two children, except for the last two levels.
(The nodes at the last level do not have children.)
New nodes are inserted at the last level from left to right.

This is called heap-structure property.

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Tremblay/L11-BinHeap.htm

• Heap is a binary tree with two special properties: it must have all its nodes in specific order and its shape must be complete.

have duplicate values in a heap — there’s no restriction against that

 The ordering of the child nodes isn’t important for a heap

A heap doesn’t follow the rules of a binary search tree; unlike binary search trees, the left node does not have to be smaller than the right node

Heap can be broadly classified in two types :

1. Min heap

2. Max heap

Min Heap

A min heap is a heap where every single parent node, including the root, is less than or equal to the value of its children nodes.

Max Heap

Every parent node, including the root, is greater than or equal to the value of its children nodes.

Heap Majorly has 3 operations –

Insert Operation(Time complexity O(log n))

Delete Operation (Time complexity O(log n))

Extract-Min (OR Extract-Max) (Time complexity O(n))

The heap data structure has many applications:

Heapsort:with no quadratic worst-case scenarios.

Selection algorithms: 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.

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 algorithm.

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

K-way merge: A heap data structure is useful to merge many already-sorted input streams into a single sorted output stream. 

Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.

https://iq.opengenus.org/max-heap-min-heap/