Heap Concept Structure and Properties in DSA Go - 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 shape property of a heap?

The shape property means the heap is a complete binary tree, where all levels are fully filled except possibly the last level, 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 must have values less than or equal to 10. For example, parent 10 with children 8 and 5 satisfies the heap property.

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, left child is at 2*i + 1, right child at 2*i + 2, and parent at (i-1)//2.

intermediate

Why is the heap structure useful for priority queues?

Because heaps allow quick access to the highest (max heap) or lowest (min heap) priority element at the root, and insertion or removal operations can be done efficiently while maintaining the heap property.

What property must a binary tree satisfy to be a heap?

A Complete binary tree and heap property

B Full binary tree only

C Balanced binary tree only

D Binary search tree property

A heap must be a complete binary tree and satisfy the heap property (max or min).

In a max heap, the root node is:

A The smallest element

B The largest element

C Random element

D The median element

In a max heap, the root node is always the largest element.

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

A i/2

B 2*i

C 2*i + 1

D i - 1

Left child index is calculated as 2*i + 1.

Which of these is NOT true about heaps?

A Heaps maintain sorted order of elements

B Heaps can be represented as arrays

C Heaps allow efficient priority access

D Heaps are complete binary trees

Heaps do not maintain sorted order, only the heap property.

What is the parent index of a node at index i in a heap array?

A i + 1

B 2*i + 1

C 2*i

D (i-1)//2

Parent index is calculated as (i-1)//2.

Describe the two main properties that define a heap data structure.

Think about the tree shape and how parent and child values relate.

Explain how a heap is stored in an array and how to find parent and child nodes using indices.

Focus on the formulas for navigating the heap in an array.