Largest 5 in array of 10 numbers without sorting

Question

Here's my code to find the max number in an array of numbers, but i can't seem to understand how to get the top 5 numbers and store them in an array and later retrieve them

Here's the code:

public class Max {


    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};
        int max = array[0]; // Assume array[0] to be the max for time-being

        //Looping n-1 times, O(n)
        for(  i = 1; i < array.length; i++) // Iterate through the First Index and compare with max
        {
            // O(1)
            if( max < array[i])
            {
                // O(1)
                max = array[i];// Change max if condition is True
                large[i] = max;
            }
        }
        for (int j = 0; j<5; j++)
        {
            System.out.println("Largest 5 : "+large[j]);
        }
        System.out.println("Largest is: "+ max);
        // Time complexity being: O(n) * [O(1) + O(1)] = O(n)
    }

}

I'm using an array to store 5 numbers, but when i run it, it is not what i want. Can anyone help me with the program?

Answer 1

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).

Answer 2

Look at the following code:

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 };
    int max = 0, index;
    for (int j = 0; j < 5; j++) {
        max = array[0];
        index = 0;
        for (i = 1; i < array.length; i++) {
            if (max < array[i]) {
                max = array[i];
                index = i;
            }
        }
        large[j] = max;
        array[index] = Integer.MIN_VALUE;

        System.out.println("Largest " + j +  " : " + large[j]);
    }
}

Note: If you don't want to change the inputted array, then make a copy of it and do the same operation on the copied array.

Take a look at Integer.MIN_VALUE.

I get the following output:

Largest 0 : 87

Largest 1 : 56

Largest 2 : 55

Largest 3 : 46

Largest 4 : 43

Answer 3

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]);
    }
}

}

Answer 4

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;
}