What is Heap

khushaalankhushaalan
1 min read

There are two types of heaps. Min heap and max heap. Height of a heap is O(log n)

Max Heap

  • Max heap is used for heapsort.

  • Value of i <= Value of parent

  • Can be represented as this array : [21, 17, 15, 14, 9, 12, 13, 8, 5, 1]

  • Root of the tree is at index 1 of the array

  • left(i) = 2*i

  • right(i) = (2*i) + 1

  • parent(i) = floor(i/2)

Min Heap

  • Min heap is used for priority queues.

  • Value of i >= Value of parent

  • Can be represented as this array : [1, 5, 8, 14, 9, 12, 13, 17, 15, 21]

  • Root of the tree is at index 1 of the array

  • left(i) = 2*i

  • right(i) = (2*i) + 1

  • parent(i) = floor(i/2)

0
Subscribe to my newsletter

Read articles from khushaalan directly inside your inbox. Subscribe to the newsletter, and don't miss out.

heap

Written by

khushaalan
khushaalan