Given a set of keys, the median key is the key in the “middle”. When the number

Question

Given a set of keys, the median key is the key in the “middle”. When the number of keys is odd, the middle key is unique. However, when the number of keys is even, there are two middle keys. We call one the lower median key and the other the upper median key. Design an ADT that supports the following methods:
InsertItem(k,e), RemoveLowerMedian(), RemoveUpperMedian().
When the ADT has n items, your implementation for the three methods should run in O(logn) time. When n is even, the items to return for RemoveLowerMedian() and RemoveUpperMedian() are obvious. When n is odd, let these methods simply return the item with the median key. Hint: Use two heaps. One is a max-heap, the other a min-heap. When n is even, the root node of the max-heap should contain the item with the lower median key; the root of the min-heap should contain the item with the upper median key. Now you work out all the details!

Explanation / Answer

public category MaxHeap
personal int[] Heap;
personal int size;
personal int maxsize;

personal static final int FRONT = 1;

public MaxHeap(int maxsize)
number.MAX_VALUE;
}

personal int parent(int pos)
come back pos / 2;
}

personal int leftChild(int pos)
come back (2 * pos);
}

personal int rightChild(int pos)
come back (2 * pos) + 1;
}

personal Boolean isLeaf(int pos)
{
if (pos >= (size / 2) && pos <= size)
come back true;
}
come back false;
}

personal void swap(int fpos,int spos)
  

personal void maxHeapify(int pos)
Heap[pos] < Heap[rightChild(pos)])
{
if (Heap[leftChild(pos)] > Heap[rightChild(pos)])
{
swap(pos, leftChild(pos));
maxHeapify(leftChild(pos));
else
  
}
}
}

public void insert(int element)
  
}

public void print()
kid : " + Heap[2*i]
+ " RIGHT kid :" + Heap[2 * i + 1]);
System.out.println();
}
}

public void maxHeap()
  
}

public int remove()
{
int popped = Heap[FRONT];
Heap[FRONT] = Heap[size--];
maxHeapify(FRONT);
come back popped;
}

public static void main(String...arg)
  

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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