Binary heap

[[toc]]

• Heap
  • Some Characteristics
    • Heap Is in the form of a binary tree
    • N-th level in heap has $2^{n-1} elements$
    • N-th level in heap has one more element than all previous level elements summed up Binary Number Characteristic <- $2^{n}=\sum_{i=0}^{n-1}{2^{i}}+1$
    • N-th levels last element in heap is the $2^{n}-1$ -th element
    • j-th element in heap is in the floor(log(j)+1) level. $2^{n}-1$ -th element in heap is at n-th level
    • left child of j-th member is at 2 * j-th position ins heap, right is at 2*j+1 -th position

Heap

• Interesting Problem
• There exits multiple types of heaps. We are talking about Binary Heap
• Binary Heap Theory

Some Characteristics

Heap Is in the form of a binary tree

N-th level in heap has $2^{n-1} elements$

N-th level in heap has one more element than all previous level elements summed up Binary Number Characteristic <- $2^{n}=\sum_{i=0}^{n-1}{2^{i}}+1$

Proof by induction

• This is correct when n=3

• Lets Perform the induction step with n+1

Left side: $2^{n+1} = 2^{n} + 2^{n}$

Right side $=\sum_{i=0}^{n}{2^{i}}+1 = 2^{n} + \sum_{i=0}^{n-1}{2^{i}}+1$

$2^{n} + 2^{n} = 2^{n} + \sum_{i=0}^{n-1}{2^{i}}+1$ <- Left Side = Right Side

N-th levels last element in heap is the $2^{n}-1$ -th element

j-th element in heap is in the floor(log(j)+1) level. $2^{n}-1$ -th element in heap is at n-th level

left child of j-th member is at 2 * j-th position ins heap, right is at 2*j+1 -th position

PROOF Last element in N-th level is $2^{n}-1$th element. In level N+1, it is $2^{n+1}-1$th element. That means, when we go to from N-th level last element to

• right child $2*2^{n}-1+1=2^{n+1}-1$ <- Last element in N+1 level
• left child $2^{n}-1=2^{n+1}-2$ <- Second to last element in N+1 level

First element in N-th level is $2^{n-1}$th element. In level N+1, it is $2^{n}$th element.

• right $2*2^{n-1}+1=2^{n}+1$ <-Second to First element in n+1 level
• left $2*2^{n-1}=2^{n}$ <- First element in n+1 level

If we go to second to last element in N-th level, it childs

• right child $2*2^{n}-2 +1=2^{n+1}-3$ <- 3. from last element in N+1 level
• left child $2^{n}-2=2^{n+1}-4$ <- 4. from last to last element in N+1 level