How to find an element in MIN/MAX heap?

Question

public class MaxMinReducer extends Reducer {
int max_sum=0; 
int mean=0;
int count=0;
Text max_occured_key=new Text();
Text mean_key=new Text("Mean : ");
Text count_key=new Text("Count : ");
int min_sum=Integer.MAX_VALUE; 
Text min_occured_key=new Text();

 public void reduce(Text key, Iterable<IntWritable> values, Context context) throws IOException, InterruptedException {
       int sum = 0;           

       for (IntWritable value : values) {
             sum += value.get();
             count++;
       }

       if(sum < min_sum)
          {
              min_sum= sum;
              min_occured_key.set(key);        
          }     


       if(sum > max_sum) {
           max_sum = sum;
           max_occured_key.set(key);
       }          

       mean=max_sum+min_sum/count;
  }

 @Override
 protected void cleanup(Context context) throws IOException, InterruptedException {
       context.write(max_occured_key, new IntWritable(max_sum));   
       context.write(min_occured_key, new IntWritable(min_sum));   
       context.write(mean_key , new IntWritable(mean));   
       context.write(count_key , new IntWritable(count));   
 }
}

Here I am writing minimum,maximum and mean of wordcount.

My input file :

high low medium high low high low large small medium

Actual output is :

high - 3------maximum

low - 3--------maximum

large - 1------minimum

small - 1------minimum

but i am not getting above output ...can anyone please help me?

Answer 1

I believe you are talking about finding min or max operation which is as follows -

Extract-Min OR Extract-Max Operation:
1. Take out the element from the root.( it will be minimum in case of Min-Heap and maximum in case of Max-Heap).
2. Take out the last element from the last level from the heap and replace the root with the element.
3. Perform Sink-Down
All delete operation must perform Sink-Down Operation.

Sink-Down Operation:
1. If replaced element is greater than any of its child node in case of Min-Heap OR smaller than any if its child node in case of Max-Heap, swap the element with its smallest child(Min-Heap) or with its greatest child(Max-Heap).
2. Keep repeating the above step, if node reaches its correct position, STOP.

C++ Implementation

public class minHeap {
    public int size;
    public int[] mH;
    public int position;

    public minHeap(int size) {
        this.size = size;
        mH = new int[size + 1]; // size+1 because index 0 will be empty
        position = 0;
    }

    public void createHeap(int[] arrA) {
        if (arrA.length > 0) {
            for (int i = 0; i < arrA.length; i++) {
                insert(arrA[i]);
            }
        }
    }

    public void display() {
        for (int i = 1; i < mH.length; i++) {
            System.out.print(" " + mH[i]);
        }
        System.out.println("");
    }

    public void insert(int x) {
        if (position == 0) { // check if Heap is empty
            mH[position + 1] = x; // insert the first element in heap
            position = 2;
        } else {
            mH[position++] = x; // insert the element to the end
            bubbleUp(); // call the bubble up operation
        }
    }

    public void bubbleUp() {
        int pos = position - 1; // last position
        while (pos > 0 && mH[pos / 2] > mH[pos]) { // check if its parent is
                                                    // greater.
            int y = mH[pos]; // if yes, then swap
            mH[pos] = mH[pos / 2];
            mH[pos / 2] = y;
            pos = pos / 2; // make pos to its parent for next iteration.
        }
    }

    public int extractMin() {
        int min = mH[1]; // extract the root
        mH[1] = mH[position - 1]; // replace the root with the last element in
                                    // the heap
        mH[position - 1] = 0; // set the last element as 0
        position--; // reduce the position pointer
        sinkDown(1); // sink down the root to its correct position
        return min;
    }

    public void sinkDown(int k) {
        int a = mH[k];
        int smallest = k;
        // check which is smaller child , 2k or 2k+1.
        if (2 * k < position && mH[smallest] > mH[2 * k]) {
            smallest = 2 * k;
        }
        if (2 * k + 1 < position && mH[smallest] > mH[2 * k + 1]) {
            smallest = 2 * k + 1;
        }
        if (smallest != k) { // if any if the child is small, swap
            swap(k, smallest);
            sinkDown(smallest); // call recursively
        }

    }

    public void swap(int a, int b) {
        // System.out.println("swappinh" + mH[a] + " and " + mH[b]);
        int temp = mH[a];
        mH[a] = mH[b];
        mH[b] = temp;
    }

    // function to delete any entry in heap
    public void delete(int x) {
        // find it and replace it with the last entry in Heap
        int index = 0;
        for (int i = 1; i < mH.length; i++) {
            if (mH[i] == x) {
                index = i;
                break;
            }
        }
        mH[index] = mH[position - 1];
        mH[position - 1] = 0; // set the last element as 0
        position--;
        sinkDown(index);
    }

    public static void main(String args[]) {
        int arrA[] = { 3, 2, 1, 7, 8, 4, 10, 16, 12 };
        System.out.print("Original Array : ");
        for (int i = 0; i < arrA.length; i++) {
            System.out.print("  " + arrA[i]);
        }
        minHeap m = new minHeap(arrA.length);
        System.out.print("\nMin-Heap : ");
        m.createHeap(arrA);
        m.display();
        m.delete(7);
        m.display();

    }
}

 Source: http://algorithms.tutorialhorizon.com/