search

swtv-kaist / cs458-fall22

1 stars 0 forks source link

About empty element #2

Open swtv-kaist opened 1 year ago

swtv-kaist commented 1 year ago

(taken from naryeong kim's post on KLMS) I think the nodes after last node should be empty to satisfy the shape property. But if the nodes can have non-positive integer, what is the value of empty node instead of zero?

Or can we think that last node is the last element of array?

swtv-kaist commented 1 year ago

what is the value of empty node instead of zero?

A value of an empty node does NOT matter (i.e., it can be any non-deterministic value) for verifying max_heapify. This is because max_heapify checks if a given node is empty or not by checking its index and h_size.

KimNaRyeong commented 1 year ago

checking its index and h_size

I didn't understand yet. For example, let the index that violates the property be 2. Then is maxheap = [0, 3, 5, 6, 7, empty, empty, empty] possible? Or should all elements of after the index be filled with integer?

swtv-kaist commented 1 year ago

let the index that violates the property be 2. Then is maxheap = [0, 3, 5, 6, 7, empty, empty, empty] possible?

Yes. Your maxheap example w/ h_size=4 is a valid input to max_heapify(...2...)