CSE310 Exam 2 2025 Questions and
Answers
What is the root index of a heap? - ANSWER-1
How is a heap stored? - ANSWER-Layer by layer, left to right
Min Heap vs Max Heap? - ANSWER-Max Heap: The parent node is greater than
or equal to the child nodes
Min Heap: The parent node is less than or equal to the child nodes
MAX-HEAPIFY(A, i) - ANSWER-Assume left and right are max heaps
Compare A[i] to A[left(i)] and A[right(i)]
If A[i] less than either, swap with the larger value child node
(IF LARGER CHILDREN EQUAL SWAP WITH LEFT)
If A[i] swapped than recursive call
BUILD-MAX-HEAP(A) - ANSWER-Starts from i = floor of length(A)/2 to 1 to
exclude all leaf nodes
COPYRIGHT ©️ 2025 ALL RIGHTS RESERVED...TRUSTED & VERIFIED 1
, Runs from bottom and goes up
BUILD-MAX-HEAP(A) runtime - ANSWER-θ(n)
Heapsort - ANSWER-Uses BUILD-MAX-HEAP(A), then from i = length(A) to 2
it swaps the first node with the last element in the array, decrementing the heap
size and calling heapify to create a sorted list
Heap-Maximum(A) - ANSWER-return largest value in max heap should be A[1]
Heap-Extract-Max(A) - ANSWER-Store value of A[1] (max)
Copy A[length(A)] to A[1]
Decrement heap size by 1
Perform Max-Heapify(A, 1)
Return stored A[1]
Increase-Key(A, i, key) - ANSWER-If key > A[1] then set A[i] = key
Compare A[i] to parent, if A[i] larger then swap and continue swapping if
necessary
Insertion(A, key) - ANSWER-Insert a new node at the end of heap with the value -
inf
call Increase-Key on the new node, where key is the key value of the node being
inserted
COPYRIGHT ©️ 2025 ALL RIGHTS RESERVED...TRUSTED & VERIFIED 2
Answers
What is the root index of a heap? - ANSWER-1
How is a heap stored? - ANSWER-Layer by layer, left to right
Min Heap vs Max Heap? - ANSWER-Max Heap: The parent node is greater than
or equal to the child nodes
Min Heap: The parent node is less than or equal to the child nodes
MAX-HEAPIFY(A, i) - ANSWER-Assume left and right are max heaps
Compare A[i] to A[left(i)] and A[right(i)]
If A[i] less than either, swap with the larger value child node
(IF LARGER CHILDREN EQUAL SWAP WITH LEFT)
If A[i] swapped than recursive call
BUILD-MAX-HEAP(A) - ANSWER-Starts from i = floor of length(A)/2 to 1 to
exclude all leaf nodes
COPYRIGHT ©️ 2025 ALL RIGHTS RESERVED...TRUSTED & VERIFIED 1
, Runs from bottom and goes up
BUILD-MAX-HEAP(A) runtime - ANSWER-θ(n)
Heapsort - ANSWER-Uses BUILD-MAX-HEAP(A), then from i = length(A) to 2
it swaps the first node with the last element in the array, decrementing the heap
size and calling heapify to create a sorted list
Heap-Maximum(A) - ANSWER-return largest value in max heap should be A[1]
Heap-Extract-Max(A) - ANSWER-Store value of A[1] (max)
Copy A[length(A)] to A[1]
Decrement heap size by 1
Perform Max-Heapify(A, 1)
Return stored A[1]
Increase-Key(A, i, key) - ANSWER-If key > A[1] then set A[i] = key
Compare A[i] to parent, if A[i] larger then swap and continue swapping if
necessary
Insertion(A, key) - ANSWER-Insert a new node at the end of heap with the value -
inf
call Increase-Key on the new node, where key is the key value of the node being
inserted
COPYRIGHT ©️ 2025 ALL RIGHTS RESERVED...TRUSTED & VERIFIED 2
