[알고리즘] 힙 (programmers.이중우선순위큐)

📌 힙 알고리즘 이란?

• 완전 이진트리 기반의 트리형 자료구조
• 최댓값, 최소값을 찾아내는데 용이
• 최대힙 : 부모가 최대 값 , 최소힙 : 부모가 최소값

📌 힙 구조 (최대 힙)

• 부모 노드가 최대 값을 가짐
• 같은 깊이 내에서 왼쪽 >= 오른쪽 값

📌 시간 복잡도

• 힙 추가,삭제 : O(log N)
• 힙 정렬 : O(N log N)
• 일반 리스트를 힙 구조로 바꾼 다고 생각했을 때 한개씩 N 개 추가함 == 힙 정렬 시간 복잡도

 

📍 사용 의의

다른 고급 정렬과 같은 시간복잡도를 가지지만, 최대 최소 원소의 삽입, 삭제가 반복해서 일어나는 경우에 대해서 힙 자료구조를 사용하면 정렬이 아닌 원소 추가, 삭제 시간 복잡도가 적용되서 효율적임

 

📌 예제 : Programmers.이중 우선순위 큐

• 힙은 자바, 코틀린 에서 우선순위 큐를 통해 구현 함
  • val minQueue = PriorityQueue<Int>()
• Default 가 최소힙이며 최대힙은 Collection.reverseOrder() 인자로 추가
  • val maxQueue = PriorityQueue<Int>(Collections.reverseOrder())

 

문제 내용

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어 수신 탑(높이)I 숫자 큐에 주어진 숫자를 삽입합니다.D 1 큐에서 최댓값을 삭제합니다.D -1 큐에서 최솟값을 삭제합니다.이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

📍 시간복잡도 비교

• 정렬 풀이
  • 반복문 : O( N ) * 정렬 : O( N log N )
• 힙 풀이
  • 반복문 : O( N ) * 추가, 삭제 : O( log N )

 

전체 풀이

import java.util.PriorityQueue
import java.util.Collections


class Solution이중우선순위큐 {

    // 최대힙과 최소힙 두개를 관리한다.
    fun solution(operations: Array<String>): IntArray {

        val minQueue = PriorityQueue<Int>()
        val maxQueue = PriorityQueue<Int>(Collections.reverseOrder())

        operations.forEach {
            val input = it.split(" ")
            if (input[0] == "I") {
                minQueue.add(input[1].toInt())
                maxQueue.add(input[1].toInt())
            } else if (minQueue.size == 0)
            else if (input[1] == "1") minQueue.remove(maxQueue.poll())
            else maxQueue.remove(minQueue.poll())
        }


        return if (maxQueue.size > 0) intArrayOf(maxQueue.peek(), minQueue.peek())
        else intArrayOf(0, 0)
    }
}