A min-max heap is a data structure that supports both deleteMin and deleteMax in
ID: 3570297 • Letter: A
Question
A min-max heap is a data structure that supports both deleteMin and deleteMax in O(log N) peroperation. The structure is identical to binary heap but the heap order property is that for any node, X, at even depth, the element is stored as X is smaller than the parent, but larger than the grandparent.
a)how do we find the minimum and maximum elements?
b)Give an algorithm to insert a new node into the min-max heap.
c)Give an algorithm to perform deleteMin and deleteMax
d)Can you build a min-max heap in linear-time?
e)suppose we would like to support deleteMin, deleteMax, and merge. Propose a data structure ro support all operations in O(log N) time.
Explanation / Answer
(a)
(b)
A node is inserted by placing it into the first available leaf position
and reestablishing the min-max heap property from the path to the root.
Here is the procedure reestablishing the property using percolateupMin and percolateUpMax():
Algorithm:
// A is the data array
// i is the position in the array
procedure PercolateUp(i)
{
if (i is on min-level)
if A[i]>A[parent(i)
swap A[i] and A[parent(i)]
// distinguish between max and min levels
PercolateUpMax(parent(i))
else PercolateUpMin(i)
// i is on max level
else
if A[i]<A[parent(i)
swap A[i] and A[parent(i)]
PercolateUpMin(parent(i))
else
PercolateUpMax(i)
}
procedure PercolateUpMin(i)
{
if A[i] has grandparent
if A[i]<A[grandparent(i)]
swap A[i] and A[parent(i)]
PercolateUpMin(grandparent(i))
}
(c)
Algorithm:
// i is the position in the array
procedure PercolateDownMin(i)
{
if (i is on min level)
PercolateDownMin(i)
else PercolateDownMax(i)
}
procedure PercolateDownMin(i)
{
if A[i] has children
m:= index of smallest of children
and grandchildren (if any) of i
//if A[m] is grandchild of i
if A[m]<A[i]
swap A[m] and A[i]
if A[m]>A[parent[m]
swap A[m] and A[parent(m)]
/* A[m] is a child of i */
PercolateDownMin(m)
else
if A[m] < A[i]
swap A[i] and A[m]
}
(d)
Yes, min and max heap can build in linear-time O(n).
C++ has the std::make_heapalgorithm.
def parent(i):
return i/2
def left(i):
return 2*i
def right(i):
return 2*i+1
def heapify_cost(n, i):
most = 0
if left(i) <= n:
most = 1 + heapify_cost(n, left(i))
if right(i) <= n:
most = 1 + max(most, heapify_cost(n, right(i)))
return most
def build_heap_cost(n):
return sum(heapify_cost(n, i) for i in xrange(n/2, 1, -1))
(e)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.