HEAP

Page 1

Heap

Heap is almost completed binary trees.

It can have one child only which says almost but everything should start from left to right.

min-heap where the root is min.

max heap: storage9)

we store it by using a linked list. The index is decided by the position in the tree. Like the tree will have 123 as s. Then the left one has (1*2) and the right is (2*n)+1 where n is the level.

To find the parent:

Divide the position by 2

how to know a given list is a heap or not?

list 24 16 13 10 8 14

1) by a.length-which is how many elements

2)by a.heapsize-how many are in a heap

here a.length is 7 and a.heapsize is 1.

defending order max heap

ascending order min-heap

to make a tree from a list

1)sort it by merge sort O(n long) but instead the given below algorithm for O(n)

2)in ascending or descending

Height of the tree

height of the longest edge to the root

Max no of nodes in terms of height

max=2^(n+1)-1 n=height

leaves to how much height

log n base 2 n=leaves here

how many leaves in tree

n=total no of nodes

n/2+1 to n

ex- if n=6

then 4to 6 are leaf nodes.

the first image is about how to change a min-heap to max heap