P. A. COLLEGE OF ENGINEERING AND TECHNOLOGY
POLLACHI, COIMBATORE – 642 002.
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
ME – DEGREE COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES AND ALGORITHMS
UNIT II – HEAP STRUCTURES
POLLACHI, COIMBATORE – 642 002.
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING
ME – DEGREE COMPUTER SCIENCE AND ENGINEERING
DATA STRUCTURES AND ALGORITHMS
Short Questions and Answers
(2 Marks )
Prepared By,
Mr. S. P. Santhoshkumar M.E.,
Assistant Professor,
Department of CSE.
(2 Marks )
Prepared By,
Mr. S. P. Santhoshkumar M.E.,
Assistant Professor,
Department of CSE.
UNIT II – HEAP STRUCTURES
1. Define Heap.
A heap is a partially ordered data
structure, and can be defined as a binary tree assigned to its nodes, one key
per node, provided the following two conditions are met
i.The tree’s shape requirement-The
binary tree is essentially complete, that is all the leaves are full except
possibly the last level, where only some rightmost leaves will be missing.
ii.The parental dominance
requirement-The key at each node is greater that or equal to the keys of its
children
2. What are the properties of binary heap?
i)
Structure Property
ii)
Heap Order Property
3.
What is a min-heap?
A
min-heap is a mirror image of the heap structure. It is a complete binary tree
in which every element is less than or equal to its children. So the root of
the min-heap contains the smallest element.
4.
what is maxheap?
If we want the elements in the
more typical increasing sorted order,we can change the ordering property so
that the parent has a larger key than the child.it is called max heap
5. What do you mean by structure property in
a heap?
A heap is a binary tree that is completely
filled with the possible exception at the
bottom level, which is filled from left to right. Such a tree is known as a
complete binary tree.
6. What do you mean by heap order property?
In a heap, for every node X, the key in the parent of X is smaller than (or
equal
to) the key in X, with the exception of the root (which has no parent).
7. What are the applications of priority
queues?
• The
selection problem
•
Event simulation
8.
What is the main use of heap?
Heaps are especially suitable for
implementing priority queues. Priority queue is a set of items with orderable
characteristic called an item’s priority, with the following operations
i. Finding an item with the highest
priority
ii.Deleting an item with highest
priority
iii.Adding
a new item to the set
9.
Give three properties of heaps?
The properties of heap are
- There exists exactly one essentially complete binary tree with ‘n’ nodes. Its height is equal to log2n
- The root of the heap is always the largest element
- A node of a heap considered with all its descendants is also a heap
10.
Give the main property of a heap that is implemented as an array.
A heap can be implemented as an array
by recording its elements in the top-down, left-to-right fashion. It is
convenient to store the heap’s elements in positions 1 through n of such an
array. In such a representation
i. The parental node keys will be in
the first n/2 positions of the array, while the leaf keys will occupy the last
n/2 positions
ii.The children of a key in the
array’s parental position ‘i’ (1≤i≤n/2) will be in positions 2i and 2i+1and
correspondingly, the parent of the key in position ‘i’(2≤i≤n) will be in
position i/2.
11.
What are the two alternatives that are used to construct a heap?
The two alternatives to construct a
heap are
- Bottom-up heap construction
- Top-down heap construction
12.
What is the algorithm to delete the root’s key from the heap?
ALGORITHM
i.Exchange the root’s key with the
last key K of the heap
ii.Decrease the heap’s size by one
iii.“Heapify” the smaller tree by
sifting K down the tree exactly in the same way as bottom-up heap construction.
Verify the parental dominance for K: if it holds stop the process, if not swap
K with the larger of its children and repeat this operation until the parental
dominance holds for K in its new position.
13. What do you mean by the term “Percolate
up”?
To insert an element, we have to create a
hole in the next available heap location.
Inserting an element in the hole would sometimes violate the heap order property, so we have to slide down the parent into the hole. This
strategy is continued until the correct location for the
new element is found. This general strategy is known as
a percolate up; the new element is percolated up the heap until the correct location is found.
14. What do you mean by the term “Percolate
down”?
When the minimum element is removed, a hole is created at
the root. Since the heap now becomes one
smaller, it follows that the last element X in the heap must move somewhere in the heap. If X can be placed in the hole, then we
are done.. This is unlikely, so we slide the smaller of
the hole’s children into the hole, thus pushing the hole
down one level. We repeat this step until X can be placed in the hole. Thus, our action is to place X in its correct spot along a path
from the root containing minimum children. This general
strategy is known as percolate down.
15. What is meant by Implicit Heaps?
A particularly simple and beautiful implementation of the heap structure is the implicit heap. Data is simply put into an array x[1...N] and the childrens of element x[i] are defined to be the elements x[2i] and x[2i+1]. Thus the parent of the element c can be found at c/2 (integer division).
16.What is a skew heap?
A heap data structure that is stored in a
binary tree (not necessarily complete and balanced). The insertion and deletion
of elements in the tree come from merging two skew heaps together in such a way
that the heap property is preserved and the tree does not degrade to a linear
tree.
17. How to
merging 2 skew heaps?
Suppose we are merging a
heap containing the elements 2, 5, and 7 with a heap containing the elements 4
and 6.
7 <- merge -> 6
/ \ /
5 2 4
i.
Identify the root, thus 7 becomes the new root and the left
subtree of the heap with root 7 becomes the
right subtree of
the other heap:
7 2
<- merge -> 6 (to form the left
subtree
\ /
of the new skew heap)
5 4
ii.
7
/ \
6
5
\
4 <-
merge -> 2
iii.
7
/ \
6
5
/ \
2 4
18. Define Fabinacci Heap.
The
Fibonacci heap is a data structure that supports all the basic heap operations
in O(1) amortized time, with the exception of delete_min and delete, which take
O (log n) amortized time. It immediately follows that the heap operations in
Dijkstra's algorithm will require a total of O(|E| + |V| log |V|) time.
Two heaps are merged only
when it is required to do so. This is similar to lazy deletion. For lazy
merging, merges are cheap, but because lazy merging does not actually combine
trees, the delete_min operation could encounter lots of trees, making that
operation expensive. Any one delete_min could take linear time, but it is
always possible to charge the time to previous merge operations. In particular,
an expensive delete_min must have been preceded by a large number of unduly
cheap merges, which have been able to store up extra potential.
20. Write the amortized analysis of Lazy Binomial Queues
To carry out the amortized analysis of lazy binomial queues, we
will use the same potential function that was used for standard binomial
queues. Thus, the potential of a lazy binomial queue is the number of trees.
21. Binomial heaps:
A set of binomial trees
satisfying the following:
1. Each binomial tree in H is heap-ordered:
the key of a node is greater than or
equal to the key of its parent
2.
There is at most one binomial tree in H whose root has a given degree
22.Write the Dijkstra’s
shortest path algorithm
Let G = (V,E) be a
weighted (weights are non-negative) undirected graph, let s Î V. Want to find the
distance (length of the shortest path), d(s,v) from s to every other vertex.
