우선순위 큐( heapq)

heapq

: heapq.heappush() :  힙에 원소를 삽입

  heapq.heappop() :   힙에서 원소를 추출

  우선순위 큐를 구현하고자 할때 사용

  (우선순위 큐 :  들어온 순서에 상관없이 원소에 우선순위를 부여해 그 우선순위가 높은 순서대로 원소를 추출하는 큐)

  

 

-파이썬-

import heapq
def heapsort(iterable):
    h=[]
    result = []
    #모든 원소를 차례대로 힙에 삽입
    for value in iterable:
        heapq.heappush(h,value) #최대힙 구현->-value
    #힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
    for i in range(len(h)):
        result.append(heapq.heappop(h)) #최대힙->-heapq.heappop(h)
    return result
result = heapsort([1,3,5,7,9,2,4,6,8,0])
print(result)

결과 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

-자바-

package 백준_java;
import java.util.PriorityQueue;
import java.util.Arrays;
public class priorityQueue {
    public static void main(String[] args){
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
        queue.add(1);
        queue.add(3);
        queue.add(5);
        queue.add(7);
        queue.add(9);
        queue.add(2);
        queue.add(4);
        queue.add(6);
        queue.add(8);
        queue.add(0);
        
        int [] heapq = new int[queue.size()];

        for(int i=0;i<heapq.length;i++){
            heapq[i] = queue.poll();
            System.out.println(heapq[i]);
            
        }
        System.out.println(Arrays.toString(heapq));
        

    }

}

결과 : [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]