Created: 2023-11-14 00:52
Status: #concept
Subject: Programming
Tags: C Data Structure Tree Linked List C Array

Heap

A data structure where each node is smaller or equal to its children (min heap), or each node is greater than its children (max heap).

  • it is a Complete Binary Tree that supports the Heap Property stated above.

Heap Illustration.png

Benefits

  1. Getting the min or max value is O(1), depending on the heap type.

Array Implementation

It is more efficient to store it in an array because we can easily search for child & parent nodes - just like Binary Trees.

  • leftChild = (2*parent) + 1
  • rightChild = (2*parent) + 2
  • parent = (child-1) / 2

Sift Operation

It makes a subtree sorted in such a way that it satisfies the Partially-ordered Tree property.

References