competitive_programming/ChefAndHisSoftware.java at master · Karthik-Ragunath/competitive_programming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
import java.io.*;
import java.util.*;
import java.lang.*;
import java.math.*;

class ChefAndHisSoftwareHeap
{
    public static void minHeapify(int[] minHeap, int size)
    {
        while((size / 2) >= 1)
        {
            if(minHeap[size / 2] > minHeap[size])
            {
                int temp = minHeap[size / 2];
                minHeap[size / 2] = minHeap[size];
                minHeap[size] = temp;
                size = size / 2;
            }
            else
            {
                break;
            }
        }
    }

    public static void minHeapifySaturated(int[] minHeap, int element, int size)
    {
        if(element > minHeap[1])
        {
            int tempSize = size - 1;
            minHeap[1] = minHeap[size];
            minHeap[size] = element;
            int currentIndex = 1;
            while((2 * currentIndex) <= tempSize)
            {
                if((2 * currentIndex + 1) <= tempSize)
                {
                    if(minHeap[2 * currentIndex] > minHeap[2 * currentIndex + 1])
                    {
                        if(minHeap[currentIndex] > minHeap[2 * currentIndex + 1])
                        {
                            int tempElement = minHeap[currentIndex];
                            minHeap[currentIndex] = minHeap[2 * currentIndex + 1];
                            minHeap[2 * currentIndex + 1] = tempElement;
                            currentIndex = 2 * currentIndex + 1;
                            continue;
                        }
                        else
                        {
                            break;
                        }
                    }
                    else
                    {
                        if(minHeap[currentIndex] > minHeap[2 * currentIndex])
                        {
                            int tempElement = minHeap[currentIndex];
                            minHeap[currentIndex] = minHeap[2 * currentIndex];
                            minHeap[2 * currentIndex] = tempElement;
                            currentIndex = 2 * currentIndex;
                            continue;
                        }
                        else
                        {
                            break;
                        }
                    }
                }
                else
                {
                    if(minHeap[currentIndex] > minHeap[2 * currentIndex])
                    {
                        int tempElement = minHeap[currentIndex];
                        minHeap[currentIndex] = minHeap[2 * currentIndex];
                        minHeap[2 * currentIndex] = tempElement;
                        currentIndex = 2 * currentIndex;
                        continue;
                    }
                    else
                    {
                        break;
                    }
                }
            }
            minHeapify(minHeap, size);
        }
    }

    public static void main(String[] args)
    {
        int testcases;
        Scanner in = new Scanner(System.in);
        testcases = in.nextInt();
        for(int i = 0; i < testcases; i++)
        {
            int minHeapSize;
            int numberOfInsertions;
            minHeapSize = in.nextInt();
            numberOfInsertions = in.nextInt();
            int[] minHeap = new int[minHeapSize + 1];
            minHeap[0] = -1;
            for(int j = 1; j <= numberOfInsertions; j++)
            {
                int element = in.nextInt();
                if(j < minHeapSize)
                {
                    minHeap[j] = element;
                    minHeapify(minHeap, j);
                    System.out.print("-1 ");
                }
                else if (j == minHeapSize)
                {
                    minHeap[j] = element;
                    minHeapify(minHeap, j);
                    System.out.print(minHeap[1] + " ");
                }
                else
                {
                    minHeapifySaturated(minHeap, element, minHeapSize);
                    System.out.print(minHeap[1] + " ");
                }
            }
            System.out.println();
        }
    }
}