Say that we want to maintain two Heaps one with the minimum at the top (and the

Question

Say that we want to maintain two Heaps one with the minimum at the top (and the children no smaller than the parent) and one with the maximum on the top (and the children no larger than the parent). We want to be able to handle the operations Delete M ax(S), Delete M in(S) and Insert(S). Use two heaps with pointers between them to be able to employ these operations in time O(log n) each.

Note: when you delete the minimum for example, then you have to delete the copy of this element in the Heap for Maximum as well. In fact the pointer between the two copies can lead to an elements in the middle of the Heap. However you have to explain how to remove a vertex from a middle of the heap.

In the algorithm, always explain how and why they work. ALWAYS, analyze the complexity of an algorithm. In all algorithms, always try to get the fastest possible.In all data structures, try to minimize as much as possible the running time of any operation.

Explanation / Answer

public class MinMaxHeap
{
private int[] Heap;
private int size;
private int maxsize;

private static final int FRONT = 1;
//constructor
public MinMaxHeap(int maxsize)
{
this.maxsize = maxsize;
this.size = 0;
Heap = new int[this.maxsize + 1];
Heap[0] = Integer.MIN_VALUE;
}
//returning parent value
private int parent(int pos)
{
return pos / 2;
}
//returning left child
private int leftChild(int pos)
{
return (2 * pos);
}
//returning right child
private int rightChild(int pos)
{
return (2 * pos) + 1;
}
//checking for leaf node or not
private boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size)
{
return true;
}
return false;
}

private void swap(int fpos, int spos)
{
int tmp;
tmp = Heap[fpos];
Heap[fpos] = Heap[spos];
Heap[spos] = tmp;
}

private void minHeapify(int pos)
{
if (!isLeaf(pos))
{
if ( Heap[pos] > Heap[leftChild(pos)] || Heap[pos] > Heap[rightChild(pos)]) //checking value is greater than or not
{
if (Heap[leftChild(pos)] < Heap[rightChild(pos)])
{
swap(pos, leftChild(pos));
minHeapify(leftChild(pos));
}else
{
swap(pos, rightChild(pos));
minHeapify(rightChild(pos));
}
}
}
}

private void maxHeapify(int pos)
{
if (!isLeaf(pos))
{
if ( Heap[pos] < Heap[leftChild(pos)] || Heap[pos] < Heap[rightChild(pos)]) //if value is less than , then swapping
{
if (Heap[leftChild(pos)] > Heap[rightChild(pos)])
{
swap(pos, leftChild(pos));
maxHeapify(leftChild(pos));
}else
{
swap(pos, rightChild(pos));
maxHeapify(rightChild(pos));
}
}
}
}

//inserting element
public void insert(int element)
{
Heap[++size] = element;
int current = size;

while (Heap[current] < Heap[parent(current)])
{
swap(current,parent(current));
current = parent(current);
}
}

public void minHeap()
{
for (int pos = (size / 2); pos >= 1 ; pos--)
{
minHeapify(pos);
}
}

public void maxHeap()
{
for (int pos = (size / 2); pos >= 1; pos--)
{
maxHeapify(pos);
}
}

public int minremove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
minHeapify(FRONT);
return popped;
}

public int maxremove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
maxHeapify(FRONT);
return popped;
}

main()
{

//creating both min and max heaps
MinMaxHeap minHeap = new MinMaxHeap(15);
MinMaxHeap maxHeap = new MinMaxHeap(15);

minHeap.insert(5);
minHeap.insert(3);
minHeap.insert(17);
minHeap.insert(10);

maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(17);
maxHeap.insert(10);

}
}

Complexity:

As it compares every time and..after some operations it can manage to get our required heap... so it takes

O(log n)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.