🤖
Data Structures and Algorithms
  • CS Theory And Problems
  • Big O
    • Big O Notation
  • Algorithms
    • Binary Search
    • Breadth First Search (BFS)
    • Depth First Search (DFS)
    • Dynamic Programming
    • Kadane's Algorithm
    • Kahn's Algorithm
    • Quickselect
    • Recursion
    • Sorting Algorithms
    • Sliding Window
  • Data Structures
    • Binary Heap
    • Graph
    • Linked List
    • Trees
  • Problems
    • LeetCode
      • 1. Two Sum
      • 3. Longest Substring Without Repeating Characters
      • 5. Longest Palindromic Substring
      • 11. Container With Most Water
      • 15. 3 Sum
      • 19. Remove Nth Node From End of List
      • 20. Valid Parentheses
      • 33. Search in Rotated Sorted Array
      • 49. Group Anagrams
      • 53. Maximum Subarray
      • 55. Jump Game
      • 56. Merge Intervals
      • 76. Minimum Window Substring
      • 98. Validate Binary Search Tree
      • 105. Construct Binary Tree from Preorder and Inorder Traversal
      • 121. Best Time to Buy and Sell Stock
      • 133. Clone Graph
      • 141. Linked List Cycle
      • 152. Maximum Product Subarray
      • 153. Find Minimum in Rotated Sorted Array
      • 200. Number of Islands
      • 206. Reverse Linked List
      • 207. Course Schedule
      • 217. Contains Duplicate
      • 226. Invert Binary Tree
      • 238. Product of Array Except Self
      • 242. Valid Anagram
      • 297. Serialize and Deserialize Binary Tree
      • 347. Top K Frequent Elements
      • 417. Pacific Atlantic Water Flow
      • 424. Longest Repeating Character Replacement
      • 435. Non-overlapping Intervals
      • 647. Palindromic Substrings
Powered by GitBook
On this page
  • Types of Heaps
  • max-heap
  • min-heap
  • Heap Rules
  • Heap properties
  • Implementation
  • Primary Operations
  • Insertion
  • Deletion
  1. Data Structures

Binary Heap

PreviousSliding WindowNextGraph

Last updated 3 years ago

A binary heap can be used as a priority queue, as the highest (or lowest) value node is always at the root of the tree.

Types of Heaps

max-heap

The value of each node is greater than all of its descendants

min-heap

The value of each node is less than all of its descendants

Heap Rules

  1. Follow its heap condition (either max-heap or min-heap)

  2. The tree must be complete

    1. It must not have any empty node positions. Although the bottom row can have empty positions. But there cannot be any nodes to the right of those empty nodes.

Example of incomplete heap (the 36 does not have a left child)

Heap properties

  • Heaps are weakly ordered.

    • It's not ordered like a binary search tree where values less than a node are on the left branch, and values greater than the node are on the right branch.

    • We only know that the descendant nodes are smaller than a given node in a max-heap. And vice versa for a min-heap.

  • In a max-heap, the greatest value will always be at the root node. In a min-heap the smallest value will be at the root node.

Implementation

  • Heaps are usually implemented as an array. This makes it easy to keep track of the root node and the last node in the 'tree'. The root node is the first element of the array. The last node is the last element of the array.

  • The first two diagrams above show how the heap is represented in the array.

  • To find the left child of a node:

    • (index * 2) + 1

  • To find the right child of a node:

    • (index * 2) + 2

  • To find the parent of a node:

    • (index - 1) / 2

      • Note: the above does integer division, so the remainder is thrown away

Primary Operations

Insertion

These steps are for a max-heap. Min-heap follows the same steps except a min comparison is done instead.

  1. A new node is inserted into the last node

  2. The new node is compared to its parent node

  3. If the new node is greater than its parent, swap the nodes

  4. repeat steps 2 - 3 until it has a parent that has a greater value than it.

Deletion

These steps are for a max-heap. Min-heap follows the same steps except a min comparison is done instead.

Important: We only ever delete the root node.

  1. Replace the root node with the last node

  2. Trickle the root node down to its proper place

    1. Check both children of the trickle down node to see which one is bigger

    2. If the trickle node is smaller than the larger of the two child nodes, then swap the trickle node with the larger child

    3. repeat above two steps until the trickle node has no descendants that have a greater value than it

By repeatedly popping the root element, we get the list in sorted order (descending). It will be in ascending order for a min-heap.

Max-Heap-new
Binary Heap with Array Implementation
Incomplete Heap