(a) List all structures that are both heaps and binary search trees. Assume that
ID: 3814013 • Letter: #
Question
(a) List all structures that are both heaps and binary search trees. Assume that all elements of the structures have different values.
(b) Use the linear-time heap creation algorithm to create a heap out of the following keys: 10 12 1 14 6 5
(c) Consider that you have a class named Heap that preserves a heap of integers using an array of int - ”elements” and an int variable named ”count”. Write a Heap method named isCorrect to check that the heap is correctly built.
(d) Write a Heap method named incrementPriority that, given the position of an element in the array just described, adds 1 to its value and reorganizes the heap if necessary. The reorganization should require no more than O(log n) operations, where n is the current number of heap elements.
Explanation / Answer
This structure will have a root and a right child(if min heap).
Max Heap of these keys created using linear algorithm is
14
12 5
10 6 1
Int isCorrect(int elements,int count,int index) {
Int left = index * 2
Int right = index *2 + 1
Int flag_left = 0
Int flag_right = 0
If (left < count) {
If (elements[left] <= elements[index])
flag_left = isCorrect(elements, count,left)
else
Return 0
If (!flag_left)
Return 0
}
Else {
If (right < count)
If (elements[right] <= elements[index])
flag_right = isCorrect(elements, count,right)
else
Return 0
If (!flag_right)
Return 0
}
Return 1
}
Above algorithm returns 1 when heap is correctly built and returns 0 otherwise.
It is called from main as isCorrect(elements,count,1)
This is a recursive algo which 1st computes index of right and left children. If indices of children fall within range then it compares current element with children to check max heap property. if it is found to be ok then it calls itself recursively on its children.
Void incrementPriority(int elements,int count,int index) {
If (index < count) {
Elements[index]++;
Int par = index/2;
While (par && elements[index] > elements[par])) {
Temp = elements[index]
Elements[index] = elements[par]
Elements[par] = temp
Index = par
Par = index/2
}
}
}
Violation occurs when value of child exceeds parent(in case of max heap).so child value is exchanged with parent value.now the new disturbing node could be parent. So comparison goes on till the root node or till there is no violation.
Please let me know in case of any doubt.
Thanks
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.