Address
Whiteland, IN 46184

Work Hours
Monday to Friday: 9AM - 5PM
Weekend: 1PM - 3PM

Binary Heap Data Structure

OBJECTIVES

  • Define what a binary heap is
  • Compare and contrast min and max heaps
  • Understand where heaps are used in the real world and what other data structures can be constructed from heaps 

What is a Binary Heap
The binary heap is much similar to the binary tree with slightly different rules. 
The Binary Heap is divided into two which are 

  • MaxBinaryHeap
  • MinBinaryHeap

MaxBinaryHeap Points

  • Each parent has at most two child nodes
  • The value of each parent node is always greater than its child nodes
  • In a max Binary Heap, the parent is greater than the children, but there are no guarantees between sibling nodes.

MinBinaryHeap Points

  • Each parent has at most two child nodes
  • The value of each parent node is always smaller than its child nodes
  • In a min Binary Heap, the parent is smaller than the children, but there are no guarantees between sibling nodes.

BigO of Binary Heap
Insertion –   O(log N)
Removal –   O(log N)
Search –   O(N)
Uses of Binary Heaps

  • Binary Heaps are used to implementing Priority Queues, which are very commonly used data structures
  • They are also used quite a bit, with graph traversal algorithms.

What is a Priority Queue
A data structure where each element has a priority. Elements with higher priorities are served before elements with lower priorities.
RECAP

  • Binary Heaps are very useful data structures for sorting and implementing other data structures like priority queues
  • Binary Heaps are either MaxBinaryHeaps or MinBinaryHeaps with parents either being smaller or larger than their children

 

Written by: Ebube Okocha

Get our Latest Insights right in your Inbox.

Enter your email address below to subscribe to our weekly newsletter.

Leave a Reply

Your email address will not be published. Required fields are marked *