binary heap

A binary heap is defined as a binary tree with two additional constraints:

shape property: a binary heap is an almost complete tree
heap property: the key stored in each node is either greater than or equal to, or less than or equal to the keys in the node's children

a heap may keep a pointer to speed up insertion, this pointer points to the leftmost leaf if the tree is complete, otherwise if its almost complete, it points to the right uncle of the rightmost leaf

in a heap the keys arent necessarily sorted like in binary search trees

bubbling

moving a node up/down a heap to get it to its correct position

bubble up

bubbling a node upwards consists of recursively switching it with its parent until its parent is bigger/smaller than it (depending on whether we're using a min heap or a max heap)

bubble down

bubbling a node downards consists of recursively switching it with one of its children until it gets to its correct position this is a pseudocode for the algorithm:

l = left(i) // index of left child
r = right(i) // index of right child
if l <= heap-size[A] and A[l] > A[i]
  largest = l
else
  largest = i
if r <= heap-size[A] and A[r] > A[largest]
  largest = r
if largest != i
  exchange A[i] A[largest]
  heapify(A, largest)

time complexity is

insertion

inserting a new node to the heap consists of adding it as a leaf such that the heap remains almost complete and bubbling up the newly added node so that the keys in the tree remain sorted

if the heap is in array representation, we insert the new node to the end of the array and heapify it upwards (bubble up)

deletion

deletion of a node consists of replacing the rightmost leaf with it and bubble it downwards if its smaller than one of its children or upwards if its bigger than its parent

binary heap array representation

some resources may use assume that arrays start at index 1, i see no point in that since most programming languages use 0 as the first index, so some of the following propositions might seem a little different like for example the proposition number 2 in the following list according to these sources would be that the left child of i^{th} node is instead of and the right child is

for an array to represent a binary heap, the only condition is that (in the case of max heap)

arrays that represent heap have the following characterstics:

root is
the parent of the i^{th} node (in the array) is
left child of the i^{th} node is
right child of the i^{th} node is

in other words, the nodes are taken from the root to the last level from left to right and put in that order in an array

the array should hold 2 values, array-size, which is the size of the array, and heap-size, which is the number of elements of the heap in the array

construction of binary heap from array

given some random array, e.g. A=[10,20,30,40,50,70,35,60,80], we need to reorganize its elements such that it represents a binary heap

to achieve this we apply bubble down to the first half of the array in reverse (because the leaf nodes need not be heapified as they already follow the heap property)

e.g. for the given array we apply bubble(A, i) such that

this is the constructing algorithm in pseudocode:

Build-Heap(A)
  n = length(A)
  heap-size = n
  for i = n/2 to 1
    heapify(A, i)

this algorithm runs in time

for we know: so for : to be continued

binary heap algorithms

biggest k nodes

initial inefficient solution:

we analyze the time complexity of this algorithm: which means that the time complexity is

we cant arrive at Big Theta for this algorithm

we suggest another algorithm that is more efficient: