Largest 5 in array of 10 numbers without sorting

The optimum data structure to retrieve top n items from a larger collection is the min/max heap and the related abstract data structure is called the priority queue. Java has an unbounded PriorityQueue which is based on the heap structure, but there is no version specialized for primitive types. It can used as a bounded queue by adding external logic, see this comment for details..

Apache Lucene has an implementation of the bounded priority queue:

http://grepcode.com/file/repo1.maven.org/maven2/org.apache.lucene/lucene-core/5.2.0/org/apache/lucene/util/PriorityQueue.java#PriorityQueue

Here is a simple modification that specializes it for ints:

/*
 * Original work Copyright 2014 The Apache Software Foundation
 * Modified work Copyright 2015 Marko Topolnik 
 * 
 * Licensed under the Apache License, Version 2.0 (the "License");
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/** A PriorityQueue maintains a partial ordering of its elements such that the
 * worst element can always be found in constant time.  Put()'s and pop()'s
 * require log(size) time.
 */
class IntPriorityQueue {
    private static int NO_ELEMENT = Integer.MIN_VALUE;
    private int size;
    private final int maxSize;
    private final int[] heap;

    IntPriorityQueue(int maxSize) {
        this.heap = new int[maxSize == 0 ? 2 : maxSize + 1];
        this.maxSize = maxSize;
    }

    private static boolean betterThan(int left, int right) {
        return left > right;
    }

    /**
     * Adds an int to a PriorityQueue in log(size) time.
     * It returns the object (if any) that was
     * dropped off the heap because it was full. This can be
     * the given parameter (in case it isn't better than the
     * full heap's minimum, and couldn't be added), or another
     * object that was previously the worst value in the
     * heap and now has been replaced by a better one, or null
     * if the queue wasn't yet full with maxSize elements.
     */
    public void consider(int element) {
        if (size < maxSize) {
            size++;
            heap[size] = element;
            upHeap();
        } else if (size > 0 && betterThan(element, heap[1])) {
            heap[1] = element;
            downHeap();
        }
    }

    public int head() {
        return size > 0 ? heap[1] : NO_ELEMENT;
    }

    /** Removes and returns the least element of the PriorityQueue in log(size)
     time. */
    public int pop() {
        if (size > 0) {
            int result = heap[1];
            heap[1] = heap[size];
            size--;
            downHeap();
            return result;
        } else {
            return NO_ELEMENT;
        }
    }

    public int size() {
        return size;
    }

    public void clear() {
        size = 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    private void upHeap() {
        int i = size;
        // save bottom node
        int node = heap[i];
        int j = i >>> 1;
        while (j > 0 && betterThan(heap[j], node)) {
            // shift parents down
            heap[i] = heap[j];
            i = j;
            j >>>= 1;
        }
        // install saved node
        heap[i] = node;
    }

    private void downHeap() {
        int i = 1;
        // save top node
        int node = heap[i];
        // find worse child
        int j = i << 1;
        int k = j + 1;
        if (k <= size && betterThan(heap[j], heap[k])) {
            j = k;
        }
        while (j <= size && betterThan(node, heap[j])) {
            // shift up child
            heap[i] = heap[j];
            i = j;
            j = i << 1;
            k = j + 1;
            if (k <= size && betterThan(heap[j], heap[k])) {
                j = k;
            }
        }
        // install saved node
        heap[i] = node;
    }
}

The way you implement betterThan decides whether it will behave as a min or max heap. This is how it's used:

public int[] maxN(int[] input, int n) {
  final int[] output = new int[n];
  final IntPriorityQueue q = new IntPriorityQueue(output.length);
  for (int i : input) {
    q.consider(i);
  }
  // Extract items from heap in sort order
  for (int i = output.length - 1; i >= 0; i--) {
    output[i] = q.pop();
  }
  return output;
}

Some interest was expressed in the performance of this approach vs. the simple linear scan from user rakeb.void. These are the results, size pertaining to the input size, always looking for 16 top elements:

Benchmark             (size)  Mode  Cnt      Score      Error  Units
MeasureMinMax.heap        32  avgt    5    270.056 ±   37.948  ns/op
MeasureMinMax.heap        64  avgt    5    379.832 ±   44.703  ns/op
MeasureMinMax.heap       128  avgt    5    543.522 ±   52.970  ns/op
MeasureMinMax.heap      4096  avgt    5   4548.352 ±  208.768  ns/op
MeasureMinMax.linear      32  avgt    5    188.711 ±   27.085  ns/op
MeasureMinMax.linear      64  avgt    5    333.586 ±   18.955  ns/op
MeasureMinMax.linear     128  avgt    5    677.692 ±  163.470  ns/op
MeasureMinMax.linear    4096  avgt    5  18290.981 ± 5783.255  ns/op

Conclusion: constant factors working against the heap approach are quite low. The breakeven point is around 70-80 input elements and from then on the simple approach loses steeply. Note that the constant factor stems from the final operation of extracting items in sort order. If this is not needed (i.e., just a set of the best items is enough), the we can simply retrieve the internal heap array directly and ignore the heap[0] element which is not used by the algorithm. In that case this solution beats one like rakib.void's even for the smallest input size (I tested with 4 top elements out of 32).

Here is a simple solution i quickly knocked up

public class Main {
public static void main(String args[]) {
    int i;
    int large[] = new int[5];
    int array[] = { 33, 55, 13, 46, 87, 42, 10, 34, 43, 56 };

    for (int j = 0; j < array.length; j++) {
        for (i = 4; i >= 0; i--) {
            if (array[j] > large[i]) {
                if (i == 4) {
                    large[i] = array[j];
                }
                else{
                    int temp = large[i];
                    large[i] = array[j];
                    large[i+1] = temp;
                }
            }
        }
    }
    for (int j = 0; j<5; j++)
    {
        System.out.println("Largest "+ j + ":"+ large[j]);
    }
}

}

Sorting, regular expressions, complex data structures are fine and make programming easy. However, I constantly see them misused nowadays and no one has to wonder:

Even if computers have become thousands of times faster over the past decades, the perceived performance still continues to not only not grow, but actually slows down. Once in your terminal application, you had instant feedback, even in Windows 3.11 or Windows 98 or Gnome 1, you often had instant feedback from your machine.

But it seems that it becomes increasingly popular to not only crack nuts with a sledgehammer, but even corns of wheat with steam hammers.

You don't need no friggin' sorting or complex datastructures for such a small problem. Don't let me invoke Z̴̲̝̻̹̣̥͎̀A̞̭̞̩̠̝̲͢L̛̤̥̲͟͜G͘҉̯̯̼̺O̦͈͙̗͎͇̳̞̕͡. I cannot take it, and even if I don't have a Java compiler at hands, here's my take in C++ (but will work in Java, too).

Basically, it initializes your 5 maxima to the lowest possible integer values. Then, it goes through your list of numbers, and for each number, it looks up into your maxima to see if it has a place there.

#include <vector>
#include <limits>    // for integer minimum
#include <iostream>  // for cout
using namespace std; // not my style, I just do so to increase readability

int main () {
    // basically, an array of length 5, initialized to the minimum integer
    vector<int> maxima(5, numeric_limits<int>::lowest());

    // your numbers
    vector<int> numbers = {33, 55, 13, 46, 87, 42, 10, 34, 43, 56};

    // go through all numbers.
    for(auto n : numbers) {

        // find smallest in maxima.
        auto smallestIndex = 0;
        for (auto m=0; m!=maxima.size(); ++m) {
            if (maxima[m] < maxima[smallestIndex]) {
                smallestIndex = m;
            }
        }

        // check if smallest is smaller than current number
        if (maxima[smallestIndex] < n)
            maxima[smallestIndex] = n;
    }

    cout << "maximum values:\n";
    for(auto m : maxima) {
        cout << " - " << m << '\n';
    }
}

It is a similar solution to rakeb.voids' answer, but flips the loops inside out and does not have to modify the input array.

Use steam hammers when appropriate only. Learn algorithms and datastructures. And know when NOT TO USE YOUR KUNG-FU. Otherwise, you are guilty of increasing the society's waste unecessarily and contribute to overall crapness.

(Java translation by Marko, signature adapted to zero allocation)

static int[] phresnel(int[] input, int[] output) {
  Arrays.fill(output, Integer.MIN_VALUE);
  for (int in : input) {
    int indexWithMin = 0;
    for (int i = 0; i < output.length; i++) {
      if (output[i] < output[indexWithMin]) {
        indexWithMin = i;
      }
    }
    if (output[indexWithMin] < in) {
      output[indexWithMin] = in;
    }
  }
  Arrays.sort(output);
  return output;
}

As an alternative to sorting, here is the logic. You figure out the code.

Keep a list (or array) of the top X values found so far. Will of course start out empty.

For each new value (iteration), check against top X list.

If top X list is shorter than X, add value.

If top X list is full, check if new value is greater than any value. If it is, remove smallest value from top X list and add new value.

Hint: Code will be better if top X list is sorted.

If you don't want to sort you can check lower number and it's position and replace. WORKING DEMO HERE.

public static void main(String[] args) {
    int array[] = {33,55,13,46,87,42,10,34,43,56};
    int mArray[] = new int[5];
    int j = 0;

    for(int i = 0; i < array.length; i++) {
        if (array[i] > lower(mArray)) {
            mArray[lowerPos(mArray)] = array[i];
        }
    }

    System.out.println(Arrays.toString(mArray));
}

public static int lower(int[] array) {
    int lower = Integer.MAX_VALUE;
    for (int n : array) {
        if (n < lower)
            lower = n;
    }
    return lower;
}

public static int lowerPos(int[] array) {
    int lower = Integer.MAX_VALUE;
    int lowerPos = 0;
    for (int n = 0; n < array.length; n++) {
        if (array[n] < lower) {
            lowerPos = n;
            lower = array[n];
        }
    }

    return lowerPos;
}

OUTPUT:

[43, 55, 56, 46, 87]

try :

public static int  getMax(int max,int[] arr ){

         int pos=0;
           //Looping n-1 times, O(n)
            for( int i = 0; i < arr.length; i++) // Iterate through the First Index and compare with max
            {
                // O(1)
                if( max < arr[i])
                {
                    // O(1)
                     max = arr[i];// Change max if condition is True
                     pos=i;

                }
            }
            arr[pos]=0;

        return max;
    }




 public static void main(String[] args)  {

            int large[]=new int[10];     
            int array[] = {33,55,13,46,87,42,10,34,43,56};

            int k=0;
            for(int i=0;i<array.length;i++){
                large[k++]=getMax(0,array);

            }

            System.out.println("Largest 5 is: "+     Arrays.toString(Arrays.copyOf(large,5)));
}

output:

Largest 5 is: [87, 56, 55, 46, 43]

Here is another approach:

public static void main(String args[]){  

     int i;
     int largestSize = 4;
     int array[] = {33,55,13,46,87,42,10,34};
     // copy first 4 elemets, they can just be the highest 
     int large[]= Arrays.copyOf(array, largestSize);
     // get the smallest value of the large array before the first start
     int smallest = large[0];
     int smallestIndex = 0;
     for (int j = 1;j<large.length;++j) {
         if (smallest > large[j]) {
             smallest = large[j];
             smallestIndex = j;
         } 
     }
     // First Loop start one elemnt after the copy
     for(i = large.length; i < array.length; i++) 
     {
         // get the smallest value and index of the large array
         if(smallest  < array[i])
         {
             large[smallestIndex] = array[i];
             // check the next smallest value
             smallest = large[0];
             smallestIndex = 0;
             for (int j = 1;j<large.length;++j) {
                 if (smallest > large[j]) {
                     smallest = large[j];
                     smallestIndex = j;
                 } 
             }
         }
     }
     for (int j = 0; j<large.length; j++)
     {
         System.out.println("Largest 5 : "+large[j]);
     }
     System.out.println();
     System.out.println("Largest is: "+ getHighest(large));

}  

private static int getHighest(int[] array) {
    int highest = array[0];
    for (int i = 1;i<array.length;++i) {
        if (highest < array[i]) {
            highest = array[i];
        }
    }
    return highest;
}

First of all, you can't use the i constant with large array. i goes up to 10, while large length is 5. Use a separate variable for that and increment when you add a new value.

Second, this logic is not retrieving the max values, you need to go over your array fully, retrieve the max value and add it to your array. Then you have to it again. You can write a first loop which use large.length as a condition and the inner loop which will use array.length. Or, you can use recursion.

You could do this properly in an OOp way. This maintains a list of the n largest values of a list of offered values.

class Largest<T extends Comparable<T>> {

    // Largest so far - null if we haven't yet seen that many.
    List<T> largest;

    public Largest(int n) {
        // Build my list.
        largest = new ArrayList(n);
        // Clear it.
        for (int i = 0; i < n; i++) {
            largest.add(i, null);
        }
    }

    public void offer(T next) {
        // Where to put it - or -1 if nowhere.
        int place = -1;
        // Must replace only the smallest replaceable one.
        T smallest = null;
        for (int i = 0; i < largest.size(); i++) {
            // What's there?
            T l = largest.get(i);
            if (l == null) {
                // Always replace null.
                place = i;
                break;
            }
            if (l.compareTo(next) < 0) {
                // Only replace the smallest.
                if (smallest == null || l.compareTo(smallest) < 0) {
                    // Remember here but keep looking in case there is a null or a smaller.
                    smallest = l;
                    place = i;
                }
            }
        }
        if (place != -1) {
            // Replace it.
            largest.set(place, next);
        }
    }

    public List<T> get() {
        return largest;
    }
}

public void test() {
    Integer array[] = {33, 55, 13, 46, 87, 42, 10, 34, 43, 56};
    Largest<Integer> l = new Largest<>(5);
    for (int i : array) {
        l.offer(i);
    }
    List<Integer> largest = l.get();
    Collections.sort(largest);
    System.out.println(largest);
    // Check it.
    List<Integer> asList = Arrays.asList(array);
    Collections.sort(asList);
    asList = asList.subList(asList.size() - largest.size(), asList.size());
    System.out.println(asList);
}

For larger numbers you can improve the algorithm using binarySearch to find the best place to put the new item instead of blindly walking the whole list. This has the added benefit of returning a sorted list.

class Largest<T extends Comparable<T>> {

    // Largest so far - null if we haven't yet seen that many.
    List<T> largest;
    // Limit.
    final int n;

    public Largest(int n) {
        // Build my list.
        largest = new ArrayList(n + 1);
        this.n = n;
    }

    public void offer(T next) {
        // Try to find it in the list.
        int where = Collections.binarySearch(largest, next, Collections.reverseOrder());
        // Positive means found.
        if (where < 0) {
            // -1 means at start.
            int place = -where - 1;
            // Discard anything beyond n.
            if (place < n) {
                // Insert here.
                largest.add(place, next);
                // Trim if necessary.
                if (largest.size() > n) {
                    largest.remove(n);
                }
            }
        }
    }

    public List<T> get() {
        return largest;
    }
}

Simple working solution for this for all condition is as given below. Please refer code below and let me know in case of any issue in comments.

public static void main(String[] args) {
    int arr[] = {75, 4, 2, 43, 56, 1,66};
    int k = 5;
    int result = find5thMaxValueApproach3(arr, k);
    System.out.println("\n 5th largest element is : " + result);
}

static int find5thMaxValueApproach3(int arr[], int k){
    int newMax = 0;
    int len = arr.length;
    int lastMax = Integer.MAX_VALUE;

    for(int j = 0; j < k; j++){

        int i = 0;
        while(arr[i] >= lastMax )
            i++;
        if(i >= len)
            break;
        
        newMax = arr[i];
        for( ; i < len; i++){
            if( arr[i] < lastMax &&  arr[i] > newMax){
                newMax = arr[i];
            }
        }
        System.out.println("newMax =" + newMax+ " lastMax="+ lastMax);
        lastMax = newMax;
    }
    return lastMax;
}