[코딩인터뷰퀘스쳔] 우선순위큐(Priority Queue)

우선순위큐(Priority Queue) 문제

- 문제11. 이진 힙에서 값 k보다 작은 모든 요소를 찾는 알고리즘을 제시하시오.

풀이) 

이진 힙의 root부터 시작하여, root의 값이 k보다 작다면 출력한 후 자식노드(left, right)를 각각 k보다 작은지 또 확인한다. 만약 또 k보다 작다면 출력하고, 각각의 노드를 root로 잡아 또 그 자식노드(left, right)로 가고.. 이런식으로 재귀적으로 호출하며, k보다 큰 수를 만나게 되면 재귀호출을 중지하고 return해준다. 직접 소스를 확인해보고 출력 결과를 보자.

소스)

public class PriorityQueue {
   private int[] array;
   private int limit;

   PriorityQueue(int[] array, int limit) {
      this.array = array;
      this.limit = limit;
   }

   int findLeftIndex(int rootIndex) {
      int index = rootIndex * 2 + 1;

      if (index >= array.length) {
         return -1;
      }

      return index;
   }

   int findRightIndex(int rootIndex) {
      int index = rootIndex * 2 + 2;

      if (index >= array.length) {
         return -1;
      }

      return index;
   }

   void recursive(int rootIndex) {
      if (rootIndex < 0) {
         return;
      }

      if (array[rootIndex] >= limit) {
         return;
      }

      if (array[rootIndex] < limit) {
         System.out.println(array[rootIndex]);

         int leftIndex = findLeftIndex(rootIndex);
         int rightIndex = findRightIndex(rootIndex);
         recursive(leftIndex);
         recursive(rightIndex);
      }
   }
}

테스트> k = 4 (각각의 노드에서 4이하의 숫자 찾아서 출력. 시작 root노드 인덱스는 0)

@Test
public void testSolve() throws Exception {
   int[] arr = {1, 2, 5, 3, 4, 6, 7};
   PriorityQueue priorityQueue = new PriorityQueue(arr, 4);
   priorityQueue.recursive(0);
}

(테스트 데이터인 arr 이진힙 형태)

               1
        2              5
     3     4        6     7

결과>

풀이 github : PriorityQueue.java , PriorityQueueTest.java