Prizes

Last Updated on March 30, 2022 by Ria Pathak

Concepts Used

Heap

Difficulty Level

Easy

Problem Statement :

Given N integers where a[i] represent that a[i]th student has won the ith competition. Print top Q students who have won the most competitions in decreasing order.

See original problem statement here

Solution Approach :

Introduction :

Idea is to create a max-heap for competitions, in order to get Q most winning students, we need to store the frequency of the winners.

Method 1 :

Calculate the frequency of these elements and store it. Now sort the array containing frequency in increasing order using any sorting algorithm. Iterate through i=Q to N, and store the Q largest values of frequencies in the array, now print Q original (corresponding) values from which we had taken differences. If at any point the frequency is same then choose the value which is largest (among the current same frequencies).

For example: Suppose our array is {5 , 5 , 2 , 2 , 3} with Q=2. The frequencies are : {2,2,1}. Sorting the frequencies in increasing order : {1,2,2}. Now taking the largest 2 frequencies :{2,2} now that the frequencies are same we will choose the largest value first which corresponds to the frequencies. 2->5, 2->2 , now printing the values as : 5 , 2.

Method 2 :

• Geneate a max-heap from the competition number & frequencies of size Q, being frequency our first priority.

• In a max-heap, the root always stores the larger value as compared to its left & right subtree, this condition needs to be true for every node. We need to insert each value one by one such that parent is always larger than the item itself. If parent is smaller, then swap the current value with its parent.

• While generating the max-heap, store the frequencies in negative values (why? we need to sort frequencies in increasing order but we are using a max-heap.). Now if our heap size goes more than Q. We will extract an value, so our heap size will be maintained.

• Now print the values corresponding to the frequencies which are stored in the heap.

extract(): Removes the maximum element from Max-Heap. Time Complexity of this Operation is O(logn) as this operation needs to maintain the heap property (by calling heapify()) after removing root.

heapify(): Maintains the heap property for each node. If any node does not follow heap property it swaps the node with the node which is smaller ,or greater (in case of max-heap), than the node.

Algorithms :

Insert():

1. Insert the item at the last index, and increment the size by 1.
2. Then, check if the inserted item is smaller than its parent,
3. If yes, then swap the inserted item with its parent.
4. If no, then do nothing.
5. Now, go to step 2 and repeat untill we reach root (first element).

Extract():

1. Store the value of the first node of our heap ( temp = heap[0] ).
2. Replace the root node with the farthest right node (last element).
3. Decrease the size by 1. (heap[0] = heap[size-1])
4. Perform heapify starting from the new root.
5. Return the stored value (temp).

Heapify () :

1. if the heap property holds true then you are done.

2. else if

3. the replacement node value > its parent nodes value
   then swap them, and repeat step 3.

4. else

5. swap the replacement node with the largest child node, and
   repeat step 3.

Example:

Solutions:

#include <bits/stdc++.h>
using namespace std;
   vector<int> solve(vector<int>& nums, int k) {
        unordered_map<int,int> numMap;
        for (auto &n : nums) {
            numMap[n]++;
        }

        priority_queue<pair<int,int>> q;
        for (auto &i : numMap) {
            q.push(make_pair(-i.second,i.first));
            if (q.size() > k) q.pop();
        }

        vector<int> result;
        while(!q.empty()) {
            result.push_back(q.top().second);
            q.pop();
        }
        return result;

    }

int main()
{  


  int t;
  cin>>t;
  while(t--)
  {
    int n,k;
    cin>>n>>k;
    vector<int> v;
    int x;
    for(int i=0;i<n;i++)
    {
      cin>>x;
      v.push_back(x);

    }
    v=solve(v,k);
    for(int i=0;i<v.size();i++)
    cout<<v[i]<<" ";
    cout<<endl;
  }

return 0;
}

import java.util.Scanner;
public class Main {
    public static class Heap {
        private class Pair {
            public int first;
            public int second;
            public Pair(int first, int second) {
                this.first = first;
                this.second = second;
            }
        }
        private Pair[] Heap;
        private int N;
        private int maxsize;
        public Heap(int maxsize) {
            this.maxsize = maxsize;
            this.Heap = new Pair[maxsize + 1];
            this.N = 0;
        }
        private boolean comp(int a, int b) {
            if (Heap[a].second == Heap[b].second) {
                return Heap[a].first < Heap[b].first;
            }
            return Heap[a].second > Heap[b].second;
        }
        public void insert(int i, int val) {
            Heap[++N] = new Pair(i, val);
            heapify_up(N);
        }
        public int size() {
            return N;
        }
        private void heapify_up(int n) {
            while (n > 1 && comp(n, n/2)) {
                swap(n, n/2);
                n = n/2;
            }
        }
        private void heapify_down(int n) {
            while (2 * n <= N) {
                int j = 2 * n;
                if (j < N && !comp(j, j+1)) j++;
                if (comp(n, j)) break;
                swap(n, j);
                n = j;
            }
        }
        public boolean isEmpty() {
            return N == 0;
        }
        public int top() {
            return Heap[1].first;
        }
        public void pop() {
            Heap[1] = Heap[N--];
            Heap[N+1] = null;
            heapify_down(1);
        }
        private void swap(int a, int b) {
            Pair temp = Heap[a];
            Heap[a] = Heap[b];
            Heap[b] = temp;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        int max = 100001;
        while(t > 0) {
            t--;
            int n = scanner.nextInt();
            int q = scanner.nextInt();
            int a[] = new int[n];
            int count[] = new int[max];
            int maximum = -1;
            for (int i=0; i<n; i++) {
                a[i] = scanner.nextInt();
                maximum = Math.max(maximum, a[i]);
                count[a[i]] += 1;
            }
            Heap heap = new Heap(maximum+1);
            for (int i=1; i<=maximum; i++) {
                heap.insert(i, count[i]);
            }
            int output[] = new int[q];
            for (int i=0; i<q; i++) {
                output[i] = heap.top();
                heap.pop();
            }
            for (int i=q-1; i >=0; i--) {
                System.out.print(output[i] + " ");
            }
            System.out.println();
        }
    }
}

[forminator_quiz id="1733"]

This article tried to discuss the concept of Heap. Hope this blog helps you understand and solve the problem. To practice more problems on heap you can check out MYCODE | Competitive Programming.