Untitled
unknown
plain_text
4 years ago
2.9 kB
7
Indexable
A priority Queue is a data structure where each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. [problem] Store the given N (2 <= N <= 100) numbers into a priority queue, then print from the highest to the lowest priority in order (assuming that there is no error in the input). [Input] The first input line contains the number of test cases, T. The next line contains the number of data input. Then, the integer data will be listed. Lower number has a higher priority. [Output] For each given test case, print the numbers in priority order. Input 2 //number of Test cases 10 //number of Input 10 49 38 17 56 92 8 1 13 55 //Input Data 13 4 22 50 13 5 1 22 35 21 7 99 100 14 Output #1 1 8 10 13 17 38 49 55 56 92 #2 1 4 5 7 13 14 21 22 22 35 50 99 100 import java.util.Scanner; class Solution { static Scanner sc; static final int MAX_SIZE = 100; static int heap[] = new int[MAX_SIZE]; static int heapSize = 0; static void heapInit() { heapSize = 0; } static void heapPush(int value) { if (heapSize + 1 > MAX_SIZE) { return; } heap[heapSize] = value; int current = heapSize; while (current > 0 && heap[current] < heap[(current - 1) / 2]) { int temp = heap[(current - 1) / 2]; heap[(current - 1) / 2] = heap[current]; heap[current] = temp; current = (current - 1) / 2; } heapSize = heapSize + 1; } static int heapPop() { if (heapSize <= 0) { return -1; } int value = heap[0]; heapSize = heapSize - 1; heap[0] = heap[heapSize]; int current = 0; while (current < heapSize && current * 2 + 1 < heapSize) { int child; if (current * 2 + 2 >= heapSize) { child = current * 2 + 1; } else { child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2; } if (heap[current] < heap[child]) { break; } int temp = heap[current]; heap[current] = heap[child]; heap[child] = temp; current = child; } return value; } static void heapPrint(int[] heap, int heap_size) { for (int i = 0; i < heap_size; i++) { System.out.print(heap[i] + " "); } System.out.println(); } public static void main(String arg[]) throws Exception { sc = new Scanner(System.in); int T = sc.nextInt(); for (int test_case = 1; test_case <= T; test_case++) { int N = sc.nextInt(); heapInit(); for (int i = 0; i < N; i++) { int value = sc.nextInt(); heapPush(value); } System.out.print("#" + test_case + " "); for (int i = 0; i < N; i++) { System.out.print(heapPop() + " "); } System.out.println(); } sc.close(); } }
Editor is loading...