# Untitled

unknown
plain_text
3 years ago
2.9 kB
3
Indexable
Never
```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();
}
}```