java - एक मेडियन-ढेर को कैसे कार्यान्वित करें



python algorithm (4)

Comocomocomocomo द्वारा प्रदान किए गए उत्तर के आधार पर मेरा कोड यहां दिया गया है:

import java.util.PriorityQueue;

public class Median {
private  PriorityQueue<Integer> minHeap = 
    new PriorityQueue<Integer>();
private  PriorityQueue<Integer> maxHeap = 
    new PriorityQueue<Integer>((o1,o2)-> o2-o1);

public float median() {
    int minSize = minHeap.size();
    int maxSize = maxHeap.size();
    if (minSize == 0 && maxSize == 0) {
        return 0;
    }
    if (minSize > maxSize) {
        return minHeap.peek();
    }if (minSize < maxSize) {
        return maxHeap.peek();
    }
    return (minHeap.peek()+maxHeap.peek())/2F;
}

public void insert(int element) {
    float median = median();
    if (element > median) {
        minHeap.offer(element);
    } else {
        maxHeap.offer(element);
    }
    balanceHeap();
}

private void balanceHeap() {
    int minSize = minHeap.size();
    int maxSize = maxHeap.size();
    int tmp = 0;
    if (minSize > maxSize + 1) {
        tmp = minHeap.poll();
        maxHeap.offer(tmp);
    }
    if (maxSize > minSize + 1) {
        tmp = maxHeap.poll();
        minHeap.offer(tmp);
    }
  }
}

अधिकतम-ढेर और न्यूनतम ढेर की तरह, मैं पूर्णांक के दिए गए सेट के औसत को ट्रैक रखने के लिए एक मध्य-ढेर को लागू करना चाहता हूं। एपीआई में निम्नलिखित तीन कार्य होना चाहिए:

insert(int)  // should take O(logN)
int median() // will be the topmost element of the heap. O(1)
int delmedian() // should take O(logN)

मैं ढेर को लागू करने के लिए एक सरणी (ए) कार्यान्वयन का उपयोग करना चाहता हूं जहां सरणी इंडेक्स के बच्चों को सरणी सूचकांक 2 * के और 2 * के + 1 में संग्रहीत किया जाता है। सुविधा के लिए, सरणी इंडेक्स 1 से तत्वों को पॉप्युलेट करने लगती है। यह है मेरे पास अब तक क्या है: मेडियन-ढेर में दो पूर्णांक होंगे जो अब तक सम्मिलित पूर्णांक की संख्या का ट्रैक रखने के लिए होंगे> वर्तमान मध्य (जीसीएम) और <वर्तमान औसत (एलसीएम) हैं।

if abs(gcm-lcm) >= 2 and gcm > lcm we need to swap a[1] with one of its children. 
The child chosen should be greater than a[1]. If both are greater, 
choose the smaller of two.

इसी तरह दूसरे मामले के लिए। तत्वों को डुबोने और तैरने के लिए मैं एल्गोरिदम के साथ नहीं आ सकता। मुझे लगता है कि इसे ध्यान में रखना चाहिए कि औसत कितना करीब है, इसलिए कुछ ऐसा है:

private void swim(int k) {
    while (k > 1 && absless(k, k/2)) {   
        exch(k, k/2);
        k = k/2;
    }
}

हालांकि मैं पूरे समाधान के साथ नहीं आ सकता।


आपको दो ढेर की आवश्यकता है: एक मिनट-ढेर और एक अधिकतम ढेर। प्रत्येक ढेर में डेटा का लगभग आधा हिस्सा होता है। न्यूनतम-ढेर में प्रत्येक तत्व औसत के बराबर या बराबर होता है, और अधिकतम-ढेर में प्रत्येक तत्व औसत के बराबर या बराबर होता है।

जब न्यूनतम ढेर में अधिकतम ढेर की तुलना में एक और तत्व होता है, तो मध्य न्यूनतम ढेर के शीर्ष पर होता है। और जब अधिकतम-ढेर में न्यूनतम ढेर की तुलना में एक और तत्व होता है, तो औसत अधिकतम ढेर के शीर्ष पर होता है।

जब दोनों ढेर में तत्वों की संख्या समान होती है, तो तत्वों की कुल संख्या भी होती है। इस मामले में आपको मध्यस्थ की अपनी परिभाषा के अनुसार चयन करना होगा: ए) दो मध्य तत्वों का अर्थ; बी) दोनों में से अधिक; सी) कम; डी) यादृच्छिक में से किसी एक को चुनें ...

हर बार जब आप सम्मिलित करते हैं, तो यह तय करने के लिए कि इसे कहां डालना है, उसके साथ नए तत्व की तुलना ढेर के शीर्ष पर करें। यदि नया तत्व वर्तमान औसत से अधिक है, तो यह न्यूनतम ढेर तक जाता है। यदि यह वर्तमान औसत से कम है, तो यह अधिकतम ढेर तक जाता है। तो आपको पुनर्वसन की आवश्यकता हो सकती है। यदि ढेर के आकार एक से अधिक तत्वों से भिन्न होते हैं, तो अधिकतम तत्वों के साथ ढेर से न्यूनतम / अधिकतम निकालें और इसे अन्य ढेर में डालें।

तत्वों की सूची के लिए औसत ढेर बनाने के लिए, हमें पहले एक रैखिक समय एल्गोरिदम का उपयोग करना चाहिए और औसत को ढूंढना चाहिए। एक बार औसत ज्ञात हो जाने के बाद, हम केवल औसत मूल्य के आधार पर न्यूनतम-ढेर और अधिकतम-ढेर में तत्व जोड़ सकते हैं। ढेर को संतुलित करना आवश्यक नहीं है क्योंकि औसत तत्वों की इनपुट सूची को बराबर हिस्सों में विभाजित कर देगा।

यदि आप एक तत्व निकालते हैं तो आपको एक तत्व को एक हीप से दूसरे में ले जाकर आकार परिवर्तन को भरने की आवश्यकता हो सकती है। इस तरह आप सुनिश्चित करते हैं कि, हर समय, दोनों ढेर में एक ही आकार होता है या केवल एक तत्व से अलग होता है।


एक पूरी तरह से संतुलित बाइनरी खोज पेड़ (बीएसटी) एक औसत ढेर नहीं है? यह सच है कि लाल-काले बीएसटी भी हमेशा पूरी तरह संतुलित नहीं होते हैं, लेकिन यह आपके उद्देश्यों के लिए पर्याप्त हो सकता है। और लॉग (एन) प्रदर्शन की गारंटी है!

एवीएल पेड़ लाल-काले बीएसटी की तुलना में अधिक कठोर रूप से संतुलित होते हैं, इसलिए वे एक असली औसत ढेर होने के करीब भी आते हैं।


यहां एक MedianHeap का एक जावा कार्यान्वयन है, जो ऊपर कॉमोकोमोकोमोमोमो के स्पष्टीकरण की सहायता से विकसित हुआ है।

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 *
 * @author BatmanLost
 */
public class MedianHeap {

    //stores all the numbers less than the current median in a maxheap, i.e median is the maximum, at the root
    private PriorityQueue<Integer> maxheap;
    //stores all the numbers greater than the current median in a minheap, i.e median is the minimum, at the root
    private PriorityQueue<Integer> minheap;

    //comparators for PriorityQueue
    private static final maxHeapComparator myMaxHeapComparator = new maxHeapComparator();
    private static final minHeapComparator myMinHeapComparator = new minHeapComparator();

    /**
     * Comparator for the minHeap, smallest number has the highest priority, natural ordering
     */
    private static class minHeapComparator implements Comparator<Integer>{
        @Override
        public int compare(Integer i, Integer j) {
            return i>j ? 1 : i==j ? 0 : -1 ;
        }
    }

    /**
     * Comparator for the maxHeap, largest number has the highest priority
     */
    private static  class maxHeapComparator implements Comparator<Integer>{
        // opposite to minHeapComparator, invert the return values
        @Override
        public int compare(Integer i, Integer j) {
            return i>j ? -1 : i==j ? 0 : 1 ;
        }
    }

    /**
     * Constructor for a MedianHeap, to dynamically generate median.
     */
    public MedianHeap(){
        // initialize maxheap and minheap with appropriate comparators
        maxheap = new PriorityQueue<Integer>(11,myMaxHeapComparator);
        minheap = new PriorityQueue<Integer>(11,myMinHeapComparator);
    }

    /**
     * Returns empty if no median i.e, no input
     * @return
     */
    private boolean isEmpty(){
        return maxheap.size() == 0 && minheap.size() == 0 ;
    }

    /**
     * Inserts into MedianHeap to update the median accordingly
     * @param n
     */
    public void insert(int n){
        // initialize if empty
        if(isEmpty()){ minheap.add(n);}
        else{
            //add to the appropriate heap
            // if n is less than or equal to current median, add to maxheap
            if(Double.compare(n, median()) <= 0){maxheap.add(n);}
            // if n is greater than current median, add to min heap
            else{minheap.add(n);}
        }
        // fix the chaos, if any imbalance occurs in the heap sizes
        //i.e, absolute difference of sizes is greater than one.
        fixChaos();
    }

    /**
     * Re-balances the heap sizes
     */
    private void fixChaos(){
        //if sizes of heaps differ by 2, then it's a chaos, since median must be the middle element
        if( Math.abs( maxheap.size() - minheap.size()) > 1){
            //check which one is the culprit and take action by kicking out the root from culprit into victim
            if(maxheap.size() > minheap.size()){
                minheap.add(maxheap.poll());
            }
            else{ maxheap.add(minheap.poll());}
        }
    }
    /**
     * returns the median of the numbers encountered so far
     * @return
     */
    public double median(){
        //if total size(no. of elements entered) is even, then median iss the average of the 2 middle elements
        //i.e, average of the root's of the heaps.
        if( maxheap.size() == minheap.size()) {
            return ((double)maxheap.peek() + (double)minheap.peek())/2 ;
        }
        //else median is middle element, i.e, root of the heap with one element more
        else if (maxheap.size() > minheap.size()){ return (double)maxheap.peek();}
        else{ return (double)minheap.peek();}

    }
    /**
     * String representation of the numbers and median
     * @return 
     */
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("\n Median for the numbers : " );
        for(int i: maxheap){sb.append(" "+i); }
        for(int i: minheap){sb.append(" "+i); }
        sb.append(" is " + median()+"\n");
        return sb.toString();
    }

    /**
     * Adds all the array elements and returns the median.
     * @param array
     * @return
     */
    public double addArray(int[] array){
        for(int i=0; i<array.length ;i++){
            insert(array[i]);
        }
        return median();
    }

    /**
     * Just a test
     * @param N
     */
    public void test(int N){
        int[] array = InputGenerator.randomArray(N);
        System.out.println("Input array: \n"+Arrays.toString(array));
        addArray(array);
        System.out.println("Computed Median is :" + median());
        Arrays.sort(array);
        System.out.println("Sorted array: \n"+Arrays.toString(array));
        if(N%2==0){ System.out.println("Calculated Median is :" + (array[N/2] + array[(N/2)-1])/2.0);}
        else{System.out.println("Calculated Median is :" + array[N/2] +"\n");}
    }

    /**
     * Another testing utility
     */
    public void printInternal(){
        System.out.println("Less than median, max heap:" + maxheap);
        System.out.println("Greater than median, min heap:" + minheap);
    }

    //Inner class to generate input for basic testing
    private static class InputGenerator {

        public static int[] orderedArray(int N){
            int[] array = new int[N];
            for(int i=0; i<N; i++){
                array[i] = i;
            }
            return array;
        }

        public static int[] randomArray(int N){
            int[] array = new int[N];
            for(int i=0; i<N; i++){
                array[i] = (int)(Math.random()*N*N);
            }
            return array;
        }

        public static int readInt(String s){
            System.out.println(s);
            Scanner sc = new Scanner(System.in);
            return sc.nextInt();
        }
    }

    public static void main(String[] args){
        System.out.println("You got to stop the program MANUALLY!!");        
        while(true){
            MedianHeap testObj = new MedianHeap();
            testObj.test(InputGenerator.readInt("Enter size of the array:"));
            System.out.println(testObj);
        }
    }
}




data-structures