Heap Concept Structure and Properties in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a heap in data structures?

A heap is a special tree-based data structure that satisfies the heap property: in a max heap, every parent node is greater than or equal to its children; in a min heap, every parent node is less than or equal to its children.

beginner

What is the difference between a max heap and a min heap?

A max heap has the largest element at the root, with each parent node greater than or equal to its children. A min heap has the smallest element at the root, with each parent node less than or equal to its children.

intermediate

How is a heap usually represented in memory?

A heap is usually represented as an array where the parent and child relationships are determined by indices: for a node at index i, its left child is at 2i + 1, and its right child is at 2i + 2.

beginner

What is the heap property?

The heap property ensures that in a max heap, every parent node is greater than or equal to its children, and in a min heap, every parent node is less than or equal to its children. This property must hold for all nodes except leaves.

intermediate

Why is a heap considered a complete binary tree?

A heap is a complete binary tree because all levels are fully filled except possibly the last level, which is filled from left to right without gaps. This structure allows efficient storage in arrays.

In a max heap, where is the largest element located?

A At any random node

B At the root node

C At the rightmost leaf

D At the leftmost leaf

In a max heap, the largest element is always at the root node because every parent is greater than or equal to its children.

How do you find the left child index of a node at index i in a heap array?

A 2 * i + 1

B 2 * i

C i / 2

D i + 1

The left child of a node at index i is at index 2 * i + 1 in the array representation of a heap.

What type of tree structure is a heap?

A Perfect binary tree

B Full binary tree

C Complete binary tree

D Binary search tree

A heap is a complete binary tree, meaning all levels are fully filled except possibly the last, which is filled from left to right.

Which property must a min heap satisfy?

A Parent nodes are less than or equal to their children

B Parent nodes are greater than their children

C All leaf nodes are greater than root

D Children nodes are always equal

In a min heap, every parent node is less than or equal to its children, ensuring the smallest element is at the root.

Why is a heap efficient for implementing priority queues?

A Because it uses linked lists internally

B Because it stores elements in sorted order

C Because it has no structure

D Because it allows quick access to the highest or lowest priority element

Heaps allow quick access to the highest (max heap) or lowest (min heap) priority element at the root, making them efficient for priority queues.

Explain the structure and key properties of a heap.

Think about how the tree is filled and how parent and child values relate.

Describe how you can find the children and parent of a node in a heap stored as an array.

Use simple math formulas based on the node's index.