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

Recall & Review

beginner

What is a heap in data structures?

A heap is a special tree-based 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 shape property of a heap?

The shape property means the heap is a complete binary tree: all levels are fully filled except possibly the last, which is filled from left to right without gaps.

beginner

Explain the heap property with an example.

In a max heap, if a parent node has value 10, its children can have values 9 and 7 but not 11. This ensures the parent is always larger or equal to children.

intermediate

How is a heap usually stored in memory?

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

intermediate

Why is a heap useful for priority queues?

Because a heap allows quick access to the highest (or lowest) priority element at the root, and insertion or removal operations can be done efficiently while maintaining heap properties.

Which property ensures a heap is a complete binary tree?

A Balance property

B Heap property

C Shape property

D Ordering property

The shape property ensures the heap is a complete binary tree, meaning all levels are fully filled except possibly the last.

In a max heap, what is true about the parent node compared to its children?

A Parent is equal or larger than children

B Parent is smaller than children

C Parent is always the smallest

D Parent has no relation to children

In a max heap, the parent node is always greater than or equal to its children.

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

A 2i + 1

B i + 1

C 2i

D i - 1

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

What kind of tree structure is a heap?

A Binary search tree

B Complete binary tree

C Full binary tree

D AVL tree

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

Why is a heap efficient for priority queue operations?

A Because it stores elements in sorted order

B Because it is a balanced binary search tree

C Because it uses linked lists

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

A heap allows quick access to the highest or lowest priority element at the root, making priority queue operations efficient.

Describe the two main properties that define a heap and explain why each is important.

Think about the tree structure and the order of values.

Explain how a heap is stored in an array and how to find the parent and children indices for any element.

Use formulas involving the index i.