[algorithm] 정렬 3. 우선순위 큐 (Priority Queues)

2024.02.04 - [Programming/Algorithm] - [algorithm] 정렬 2. 퀵 정렬

[algorithm] 정렬 2. 퀵 정렬

 

이어지는 포스팅이다.

 

 

목차

• 우선순위 큐 (Priority Queues)
• 기초적인 구현
• 힙 (Heap)
• 힙 알고리즘 구현하기
• 힙을 이용한 알고리즘 1 : 인덱스 기반 우선순위 큐
• 힙을 이용한 알고리즘 2 : 힙 정렬

 

 큐 (Queue)는 FIFO (First-in-first-out)을 기반으로 하는 자료구조다. 기본적으로 가장 먼저 in 한 항목이 가장 먼저 out 하는 방식이다. 반대로 큐에 넣은 항목 중 가장 높은 우선순위 (최댓값, 최솟값 등)에 해당하는 항목을 꺼내게 할 수 있는 자료구조가 있다. 이 자료구조가 우선순위 큐이다. 특히 우선순위 큐를 구현할 때 사용되는 힙 (heap) 자료구조는 현대 응용 환경에서 매우 중요해지고 있다.

---

우선순위 큐 (Priority Queues)

 우선순위 큐란 최댓값 항목 삭제(꺼내기), 새로운 항목 추가 작업 (삽입)을 지원하는 Queue 데이터 타입이다.  우선순위 큐는 보통 이진 힙 (binary heap)으로 구현할 수 있으며, 전통적인 우선순위 큐 구현형태로 배열에 항목들을 저장하되, 삽입, 최댓값 삭제 작업이 logN 안으로 구현되도록 한다. 

 

 우선순위 큐는 꼭 모든 키를 정렬할 필요가 없는 알고리즘을 구현할 때 유용하다. 예를 들면, 스마트폰의 여러 프로세스가 실행되고 있을 때 전화가 오면 전화 앱이 최우선으로 구동되는 경우가 있다. 굳이 현재 구동되는 모든 프로세스의 우선순위를 정렬한 다음 전화 앱을 최우선으로 구동해야 할까? 작업 스케쥴링 시 우선순위가 가장 높은 작업을 최우선으로 처리하는 알고리즘이 우선순위 큐  (Priority Queues)를 사용한 정렬 알고리즘이다. 우선순위 큐를 사용하면 항목들을 모두 큐에 넣고, 순차적으로 꺼내는거 자체가 정렬이 되는 과정으로 쓸 수도 있다. 

 

API

 크게 2가지 연산이 있다.

• 최댓값 항목 삭제 (꺼내기) delMax() : 배열에서 가장 큰 키값을 삭제
• 새로운 항목 삽입 insert()

우선순위 큐 API

 

우선순위 큐 클라이언트

 클라이언트의 예로 매우 큰 N개의 문자열을 스트림 형태로 입력받고, 가장 긴 M개의 문자열을 출력하는 것을 들 수 있다. 스트림은 금융 거래정보, 서비스 request, 과학 실험 결과같이 계속해서 들어오는 데이터들을 의미한다. 즉 스트림은 데이터의 크기가 무제한이다.

 

 그렇기 때문에, 스트림을 모두 정렬하는 것 자체가 매우 비효율 적이다. 따라서 크기 M의 가장 큰 항목을 저장하는 우선순위 큐를 유지시키는 접근방법을 사용한다.

 

public class TopM {

    public static void main(String[] args) {
        // 입력 스트림에서 최댓값 항목 M개의 라인을 출력
        int M = Integer.parseInt(args[0]);
        MinPQ<Transaction> pq = new MinPQ<Transaction>(M + 1); // 최댓값 M개의 항목을 저장하는 우선순위 큐

        while (StdIn.hasNextLine()) {
            // 우선순위 큐에 M개 이상의 항목이 들어가면 가장 작은 항목을 삭제
            pq.insert(new Transaction(StdIn.readLine()));
            if (pq.size() > M) {
                pq.delMin(); // 가장 작은 항목 삭제
            }
        }
        
        Stack<Transaction> stack = new Stack<Transaction>();
        while (!pq.isEmpty()) {
            stack.push(pq.delMin());
        }

        stack.forEach(System.out::println);
    }
}

---

기초적인 구현

데이터 구조	삽입	최댓값 항목 삭제
정렬된 배열	N	1
정렬되지 않은 배열	1	N
힙 (heap)	logN	logN

 

 정렬된 배열 구조를 사용하는 방법은 삽입 (push()) 할 때마다 정렬 작업을 수행하는 것이다. (Eager) 정렬되지 않은 배열 구조를 사용하는 것은 필요 시점까지 (pop()) 정렬 작업을 미루는 방법이다. 둘은 trade-off 관계에 있다.  반면 (Lazy) 힙 구조는 삽입/삭제 모두 logN 시간을 보증할 수 있게 한다.

 

정렬되지 않은 배열을 사용한 구현

 stack을 기반으로 단순하게 구현한다. 

• 삽입 : stack에 push()
• 최댓값 항목 삭제
  • 내부 루프에서 선택 정렬을 사용해 최댓값 키 찾기
  • stack의 pop()에서 항목 삭제 구현

정렬된 배열을 사용한 구현

최댓값이 항상 오른쪽 끝에 위치하도록 유지시킨다.

• 삽입 : 큰 항목을 우측으로 한칸 씩 이동시켜 배열을 정렬된 상태로 유지
• 최댓값 항목 삭제 : stack의 pop()

---

힙 (Heap)

 이진 힙 (binary heap)은 우선순위 큐의 기본동작을 효율적일 수 있게 하는 자료구조다. 배열에 키들을 저장 시 자신과 연결된 다른 두키보다 크거나 같도록 유지시킨다. (마치 이진트리에서 자식 노드가 항상 자기보다 작거나 같도록 하는 것)

 이진 트리에서 두 자식 노드가 부모노드보다 작거나 같으면 이 이진트리는 힙-정렬되었다고 한다. 힙 정렬된 이진트리에서 가장 큰 키는 루트노드다.

힙 정렬된 이진 힙

 이진 힙은 트리로 표현하는 것이 가장 적절하다. 키마다 총 3개의 링크가 필요하다. (상위 1, 하위 2) 루트 노드를 위치시키고, 아래로 (왼->오) 내려가면서 자식 노드를 위치시켜 나간다. 따라서 이진 힙은 힙 정렬된 이진트리 노드들이 레벨 순서대로 나열된 배열이다.

• 루트 노드 : a[1] 
• 부모 노드 : a[k]
• 자식 노드 : a [2k], a [2k+1]

 크기가 N인 완전 이진트리의 높이는 logN에 가깝다. 그러므로 삽입, 최대 항목 삭제를 logN을 보증하게 할 수 있고, 포인터가 필요 없이 트리 위아래 탐색 시 logN을 보증한다.

 

다중 힙

 이진 힙이 아닌 그 이상으로 (e.g. 3중 트리) 힙을 생성할 수 있다. 만일 3중 힙이라면 배열은 아래처럼 구성된다.

• 루트 노드 : a [1]
• 부모 노드 : a [k]
• 자식노드 : a [3k-1], a [3k], a [3k+1]

 d 중 트리일 때, d 가 클수록 트리의 높이는 낮아지기 때문에 루트 노드에서 리프노드까지의 거리가 짧아진다. 그러나 같은 레벨 안에서 최대 값을 찾는 비용이 증가된다. (trade off)

 

배열 크기 조정

 클라이언트는 힙의 크기를 신경 쓰지 않아야 한다. 따라서 원소 삽입, 삭제 시 배열의 크기를 필요 때마다 2배씩 늘리고 줄이게 구현한다.

 

키 값의 불변성

 힙을 구성할 때 키의 값은 변경할 수 없다고 가정해야 한다. 키 값을 수정하는 순간 힙의 정렬이 어긋날 수 있다. 클라이언트가 무슨 짓을 하건 힙의 정렬이 유지될 수 있도록 키 값은 변경되지 못하도록 해야한다.

---

힙 알고리즘 구현하기

 크기가 N인 힙은 크기가 N+1인 배열 pq []를 사용한다. (pq [1] ~ pq [N] : 힙의 실제 원소) 어떤 작업이 있고 난 뒤 다시 힙-정렬이 되도록 하는 작업을 힙 복구 작업 (reheapifying)이라 한다. 

// 원소 i와 j 비교
private boolean less(int i, int j){
    return pq[i].compareTo(pq[j]) < 0;
}

// 원소 i와 j 교환
private void exch(int i, int j){
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}

 

 이진 힙에 새로운 노드가 추가될 수도 있고, 노드의 내부 값이 수정될 수도 있다. 

• 경우의 수 1 : 특정 노드의 우선순위가 증가되면 (리프 노드에 새로운 노드가 추가된 경우), 힙을 거슬러 올라가며 힙의 순서 수정
• 경우의 수 2 : 특정 노드의 우선순위가 낮아지면 (리프 노드의 값을 더 작은 값으로 수정), 힙을 내려가면서 힙의 순서 수정

 

상향식 힙 복구 (swim) : 원소 삽입 시

상향식 힙 복구 예제

 

 T로 값이 수정되면서 상향식 힙 복구를 진행한 예제이다.  특정 노드가 부모 노드보다 커졌을 때 상향식 힙 복구를 진행한다. 복구 방법은 아래와 같다

1. 해당 노드를 부모 노드와 교환
2. 교환 후 해당 노드는 자식 노드보다 같거나 큰 상태가 됨
3. 그래도 해당 노드의 부모노드보다 크면 재귀적으로 교환 (더 큰 부모 노드를 만나거나, 루트노드를 만나면 중단)

 회사 조직도에서 경력직 신규 사원이 입사한 경우와 비슷하다. 우선 신규 사원을 조직도 제일 끝 (배열의 마지막 원소)에 배치한다. 그 후 신규 사원의 직급에 맞는 위치를 찾을 때까지 반복해서 위로 승격 시켜 나간다. 

// 상향식 힙 복구 구현
// k : 복구해야하는 노드의 인덱스 k
private void swim(int k){

    // (루트노드가 아님 and 부모보다 큰 경우) 반복
    while (k > 1 && less(k/2, k)) {
        exch(k/2, k); // 부모와 교환
        k = k/2;
    }
}

 

하향식 힙 복구 (sink) : 최대 항목 삭제 시

하향식 힙 복구 예제

 해당 노드가 자식 노드 중 하나보다 작아졌을 때 발생한다. 해당 노드를 자식 노드 중에 더 큰 노드와 교환해 나가면서 하향식 힙 복구를 진행한다.

 

1. 해당 노드를 자식 노드 중 더 큰 노드와 교환
2. 교환 후 해당 노드가 새로운 자식 노드보다 작다면 재귀적으로 교환 (두 자식 노드가 모두 해당 노드보다 작거나 같아지면 중단)

 회사 조직도에서 기존의 사장이 사임한 뒤, 새로운 사장이 입사했을 때와 비슷하다. 일단 새로운 사장을 사장 자리에 두고, 사장보다 일 잘하는 사람을 만나면 계속해서 하향식으로 내려가면서 사장을 강등시킨다.

// 하향식 힙 복구의 구현
// k : 복구해야하는 노드의 인덱스 k
private void sink(int k){
    
    // 자식노드보다 같거나 작으면 반복
    while (2*k <= N) {
        int j = 2*k; // 자식 노드
        if(j < N && less(j, j+1)) j++; //자식노드랑 비교 후, 형제노드와 비교
        if(!less(k, j)) break; //자식노드보다 크면 break
         
        exch(k, j); // 자식이랑 교환
        k = j;
    }
}

 

삽입 (좌), 최대항목 삭제 (우)

 

알고리즘 동작 과정

 

우선순위 큐 (힙) 코드

/*
 * Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne.
 * Last updated: Thu Aug 11 09:07:21 EDT 2022.
 */

import org.algorithm.lib.StdIn;
import org.algorithm.lib.StdOut;

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * The {@code MaxPQ} class represents a priority queue of generic keys.
 * It supports the usual <em>insert</em> and <em>delete-the-maximum</em>
 * operations, along with methods for peeking at the maximum key,
 * testing if the priority queue is empty, and iterating through
 * the keys.
 * <p>
 * This implementation uses a <em>binary heap</em>.
 * The <em>insert</em> and <em>delete-the-maximum</em> operations take
 * &Theta;(log <em>n</em>) amortized time, where <em>n</em> is the number
 * of elements in the priority queue. This is an amortized bound
 * (and not a worst-case bound) because of array resizing operations.
 * The <em>min</em>, <em>size</em>, and <em>is-empty</em> operations take
 * &Theta;(1) time in the worst case.
 * Construction takes time proportional to the specified capacity or the
 * number of items used to initialize the data structure.
 * <p>
 * For additional documentation, see
 * <a href="https://algs4.cs.princeton.edu/24pq">Section 2.4</a> of
 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 * @param <Key> the generic type of key on this priority queue
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */

public class MaxPQ<Key> implements Iterable<Key> {
    private Key[] pq;                    // store items at indices 1 to n
    private int n;                       // number of items on priority queue
    private Comparator<Key> comparator;  // optional comparator

    /**
     * Initializes an empty priority queue with the given initial capacity.
     *
     * @param initCapacity the initial capacity of this priority queue
     */
    public MaxPQ(int initCapacity) {
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }

    /**
     * Initializes an empty priority queue.
     */
    public MaxPQ() {
        this(1);
    }

    /**
     * Initializes an empty priority queue with the given initial capacity,
     * using the given comparator.
     *
     * @param initCapacity the initial capacity of this priority queue
     * @param comparator   the order in which to compare the keys
     */
    public MaxPQ(int initCapacity, Comparator<Key> comparator) {
        this.comparator = comparator;
        pq = (Key[]) new Object[initCapacity + 1];
        n = 0;
    }

    /**
     * Initializes an empty priority queue using the given comparator.
     *
     * @param comparator the order in which to compare the keys
     */
    public MaxPQ(Comparator<Key> comparator) {
        this(1, comparator);
    }

    /**
     * Initializes a priority queue from the array of keys.
     * Takes time proportional to the number of keys, using sink-based heap construction.
     *
     * @param keys the array of keys
     */
    public MaxPQ(Key[] keys) {
        n = keys.length;
        pq = (Key[]) new Object[keys.length + 1];
        for (int i = 0; i < n; i++)
            pq[i + 1] = keys[i];
        for (int k = n / 2; k >= 1; k--)
            sink(k);
        assert isMaxHeap();
    }


    /**
     * Returns true if this priority queue is empty.
     *
     * @return {@code true} if this priority queue is empty;
     * {@code false} otherwise
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * Returns the number of keys on this priority queue.
     *
     * @return the number of keys on this priority queue
     */
    public int size() {
        return n;
    }

    /**
     * Returns a largest key on this priority queue.
     *
     * @return a largest key on this priority queue
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key max() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    // resize the underlying array to have the given capacity
    private void resize(int capacity) {
        assert capacity > n;
        Key[] temp = (Key[]) new Object[capacity];
        for (int i = 1; i <= n; i++) {
            temp[i] = pq[i];
        }
        pq = temp;
    }


    /**
     * Adds a new key to this priority queue.
     *
     * @param x the new key to add to this priority queue
     */
    public void insert(Key x) {

        // double size of array if necessary
        if (n == pq.length - 1) resize(2 * pq.length);

        // add x, and percolate it up to maintain heap invariant
        pq[++n] = x;
        swim(n);
        assert isMaxHeap();
    }

    /**
     * Removes and returns a largest key on this priority queue.
     *
     * @return a largest key on this priority queue
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key delMax() {
        if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
        Key max = pq[1];
        exch(1, n--);
        sink(1);
        pq[n + 1] = null;     // to avoid loitering and help with garbage collection
        if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
        assert isMaxHeap();
        return max;
    }


    /***************************************************************************
     * Helper functions to restore the heap invariant.
     ***************************************************************************/

    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k / 2, k);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(j, j + 1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }

    /***************************************************************************
     * Helper functions for compares and swaps.
     ***************************************************************************/
    private boolean less(int i, int j) {
        if (comparator == null) {
            return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
        } else {
            return comparator.compare(pq[i], pq[j]) < 0;
        }
    }

    private void exch(int i, int j) {
        Key swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
    }

    // is pq[1..n] a max heap?
    private boolean isMaxHeap() {
        for (int i = 1; i <= n; i++) {
            if (pq[i] == null) return false;
        }
        for (int i = n + 1; i < pq.length; i++) {
            if (pq[i] != null) return false;
        }
        if (pq[0] != null) return false;
        return isMaxHeapOrdered(1);
    }

    // is subtree of pq[1..n] rooted at k a max heap?
    private boolean isMaxHeapOrdered(int k) {
        if (k > n) return true;
        int left = 2 * k;
        int right = 2 * k + 1;
        if (left <= n && less(k, left)) return false;
        if (right <= n && less(k, right)) return false;
        return isMaxHeapOrdered(left) && isMaxHeapOrdered(right);
    }


    /***************************************************************************
     * Iterator.
     ***************************************************************************/

    /**
     * Returns an iterator that iterates over the keys on this priority queue
     * in descending order.
     * The iterator doesn't implement {@code remove()} since it's optional.
     *
     * @return an iterator that iterates over the keys in descending order
     */
    public Iterator<Key> iterator() {
        return new HeapIterator();
    }

    private class HeapIterator implements Iterator<Key> {

        // create a new pq
        private MaxPQ<Key> copy;

        // add all items to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            if (comparator == null) copy = new MaxPQ<Key>(size());
            else copy = new MaxPQ<Key>(size(), comparator);
            for (int i = 1; i <= n; i++)
                copy.insert(pq[i]);
        }

        public boolean hasNext() {
            return !copy.isEmpty();
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Key next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMax();
        }
    }

    /**
     * Unit tests the {@code MaxPQ} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        MaxPQ<String> pq = new MaxPQ<String>();
        while (!StdIn.isEmpty()) {
            String item = StdIn.readString();
            if (!item.equals("-")) pq.insert(item);
            else if (!pq.isEmpty()) StdOut.print(pq.delMax() + " ");
        }
        StdOut.println("(" + pq.size() + " left on pq)");
    }

}

---

힙을 이용한 알고리즘 1 : 인덱스 기반 우선순위 큐

 

 클라이언트가 큐의 항목에 인덱스를 통해 직접 접근해야 할 수도 있다. 이때는 각 항목 (노드)마다 정수로된 식별자를 부여해 인덱스 값으로 활용할 수 있다. 

인덱스를 적용한 우선순위 큐 API

package org.algorithm.sorting;

/*
 * Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne.
 * Last updated: Thu Aug 11 09:08:08 EDT 2022.
 */

import org.algorithm.lib.StdOut;
import org.algorithm.lib.StdRandom;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * The {@code IndexMaxPQ} class represents an indexed priority queue of generic keys.
 * It supports the usual <em>insert</em> and <em>delete-the-maximum</em>
 * operations, along with <em>delete</em> and <em>change-the-key</em>
 * methods. In order to let the client refer to items on the priority queue,
 * an integer between {@code 0} and {@code maxN - 1}
 * is associated with each key—the client
 * uses this integer to specify which key to delete or change.
 * It also supports methods for peeking at a maximum key,
 * testing if the priority queue is empty, and iterating through
 * the keys.
 * <p>
 * This implementation uses a <em>binary heap</em> along with an
 * array to associate keys with integers in the given range.
 * The <em>insert</em>, <em>delete-the-maximum</em>, <em>delete</em>,
 * <em>change-key</em>, <em>decrease-key</em>, and <em>increase-key</em>
 * operations take &Theta;(log <em>n</em>) time in the worst case,
 * where <em>n</em> is the number of elements in the priority queue.
 * Construction takes time proportional to the specified capacity.
 * <p>
 * For additional documentation, see
 * <a href="https://algs4.cs.princeton.edu/24pq">Section 2.4</a> of
 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 * @param <Key> the generic type of key on this priority queue
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */
public class IndexMaxPQ<Key extends Comparable<Key>> implements Iterable<Integer> {
    private int maxN;        // maximum number of elements on PQ
    private int n;           // number of elements on PQ
    private int[] pq;        // binary heap using 1-based indexing
    private int[] qp;        // inverse of pq - qp[pq[i]] = pq[qp[i]] = i
    private Key[] keys;      // keys[i] = priority of i

    /**
     * Initializes an empty indexed priority queue with indices between {@code 0}
     * and {@code maxN - 1}.
     *
     * @param maxN the keys on this priority queue are index from {@code 0} to {@code maxN - 1}
     * @throws IllegalArgumentException if {@code maxN < 0}
     */
    public IndexMaxPQ(int maxN) {
        if (maxN < 0) throw new IllegalArgumentException();
        this.maxN = maxN;
        n = 0;
        keys = (Key[]) new Comparable[maxN + 1];    // make this of length maxN??
        pq = new int[maxN + 1];
        qp = new int[maxN + 1];                   // make this of length maxN??
        for (int i = 0; i <= maxN; i++)
            qp[i] = -1;
    }

    /**
     * Returns true if this priority queue is empty.
     *
     * @return {@code true} if this priority queue is empty;
     * {@code false} otherwise
     */
    public boolean isEmpty() {
        return n == 0;
    }

    /**
     * Is {@code i} an index on this priority queue?
     *
     * @param i an index
     * @return {@code true} if {@code i} is an index on this priority queue;
     * {@code false} otherwise
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     */
    public boolean contains(int i) {
        validateIndex(i);
        return qp[i] != -1;
    }

    /**
     * Returns the number of keys on this priority queue.
     *
     * @return the number of keys on this priority queue
     */
    public int size() {
        return n;
    }

    /**
     * Associate key with index i.
     *
     * @param i   an index
     * @param key the key to associate with index {@code i}
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if there already is an item
     *                                  associated with index {@code i}
     */
    public void insert(int i, Key key) {
        validateIndex(i);
        if (contains(i)) throw new IllegalArgumentException("index is already in the priority queue");
        n++;
        qp[i] = n;
        pq[n] = i;
        keys[i] = key;
        swim(n);
    }

    /**
     * Returns an index associated with a maximum key.
     *
     * @return an index associated with a maximum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public int maxIndex() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        return pq[1];
    }

    /**
     * Returns a maximum key.
     *
     * @return a maximum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public Key maxKey() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        return keys[pq[1]];
    }

    /**
     * Removes a maximum key and returns its associated index.
     *
     * @return an index associated with a maximum key
     * @throws NoSuchElementException if this priority queue is empty
     */
    public int delMax() {
        if (n == 0) throw new NoSuchElementException("Priority queue underflow");
        int max = pq[1];
        exch(1, n--);
        sink(1);

        assert pq[n + 1] == max;
        qp[max] = -1;        // delete
        keys[max] = null;    // to help with garbage collection
        pq[n + 1] = -1;        // not needed
        return max;
    }

    /**
     * Returns the key associated with index {@code i}.
     *
     * @param i the index of the key to return
     * @return the key associated with index {@code i}
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws NoSuchElementException   no key is associated with index {@code i}
     */
    public Key keyOf(int i) {
        validateIndex(i);
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        else return keys[i];
    }

    /**
     * Change the key associated with index {@code i} to the specified value.
     *
     * @param i   the index of the key to change
     * @param key change the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     */
    public void changeKey(int i, Key key) {
        validateIndex(i);
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        keys[i] = key;
        swim(qp[i]);
        sink(qp[i]);
    }

    /**
     * Change the key associated with index {@code i} to the specified value.
     *
     * @param i   the index of the key to change
     * @param key change the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @deprecated Replaced by {@code changeKey(int, Key)}.
     */
    @Deprecated
    public void change(int i, Key key) {
        validateIndex(i);
        changeKey(i, key);
    }

    /**
     * Increase the key associated with index {@code i} to the specified value.
     *
     * @param i   the index of the key to increase
     * @param key increase the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if {@code key <= keyOf(i)}
     * @throws NoSuchElementException   no key is associated with index {@code i}
     */
    public void increaseKey(int i, Key key) {
        validateIndex(i);
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) == 0)
            throw new IllegalArgumentException("Calling increaseKey() with a key equal to the key in the priority queue");
        if (keys[i].compareTo(key) > 0)
            throw new IllegalArgumentException("Calling increaseKey() with a key that is strictly less than the key in the priority queue");

        keys[i] = key;
        swim(qp[i]);
    }

    /**
     * Decrease the key associated with index {@code i} to the specified value.
     *
     * @param i   the index of the key to decrease
     * @param key decrease the key associated with index {@code i} to this key
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws IllegalArgumentException if {@code key >= keyOf(i)}
     * @throws NoSuchElementException   no key is associated with index {@code i}
     */
    public void decreaseKey(int i, Key key) {
        validateIndex(i);
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        if (keys[i].compareTo(key) == 0)
            throw new IllegalArgumentException("Calling decreaseKey() with a key equal to the key in the priority queue");
        if (keys[i].compareTo(key) < 0)
            throw new IllegalArgumentException("Calling decreaseKey() with a key that is strictly greater than the key in the priority queue");
        keys[i] = key;
        sink(qp[i]);
    }

    /**
     * Remove the key on the priority queue associated with index {@code i}.
     *
     * @param i the index of the key to remove
     * @throws IllegalArgumentException unless {@code 0 <= i < maxN}
     * @throws NoSuchElementException   no key is associated with index {@code i}
     */
    public void delete(int i) {
        validateIndex(i);
        if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue");
        int index = qp[i];
        exch(index, n--);
        swim(index);
        sink(index);
        keys[i] = null;
        qp[i] = -1;
    }

    // throw an IllegalArgumentException if i is an invalid index
    private void validateIndex(int i) {
        if (i < 0) throw new IllegalArgumentException("index is negative: " + i);
        if (i >= maxN) throw new IllegalArgumentException("index >= capacity: " + i);
    }

    /***************************************************************************
     * General helper functions.
     ***************************************************************************/
    private boolean less(int i, int j) {
        return keys[pq[i]].compareTo(keys[pq[j]]) < 0;
    }

    private void exch(int i, int j) {
        int swap = pq[i];
        pq[i] = pq[j];
        pq[j] = swap;
        qp[pq[i]] = i;
        qp[pq[j]] = j;
    }


    /***************************************************************************
     * Heap helper functions.
     ***************************************************************************/
    private void swim(int k) {
        while (k > 1 && less(k / 2, k)) {
            exch(k, k / 2);
            k = k / 2;
        }
    }

    private void sink(int k) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(j, j + 1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }


    /**
     * Returns an iterator that iterates over the keys on the
     * priority queue in descending order.
     * The iterator doesn't implement {@code remove()} since it's optional.
     *
     * @return an iterator that iterates over the keys in descending order
     */
    public Iterator<Integer> iterator() {
        return new HeapIterator();
    }

    private class HeapIterator implements Iterator<Integer> {
        // create a new pq
        private IndexMaxPQ<Key> copy;

        // add all elements to copy of heap
        // takes linear time since already in heap order so no keys move
        public HeapIterator() {
            copy = new IndexMaxPQ<Key>(pq.length - 1);
            for (int i = 1; i <= n; i++)
                copy.insert(pq[i], keys[pq[i]]);
        }

        public boolean hasNext() {
            return !copy.isEmpty();
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public Integer next() {
            if (!hasNext()) throw new NoSuchElementException();
            return copy.delMax();
        }
    }

    /**
     * Unit tests the {@code IndexMaxPQ} data type.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        // insert a bunch of strings
        String[] strings = {"it", "was", "the", "best", "of", "times", "it", "was", "the", "worst"};

        IndexMaxPQ<String> pq = new IndexMaxPQ<String>(strings.length);
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }

        // print each key using the iterator
        for (int i : pq) {
            StdOut.println(i + " " + strings[i]);
        }

        StdOut.println();

        // increase or decrease the key
        for (int i = 0; i < strings.length; i++) {
            if (StdRandom.bernoulli(0.5))
                pq.increaseKey(i, strings[i] + strings[i]);
            else
                pq.decreaseKey(i, strings[i].substring(0, 1));
        }

        // delete and print each key
        while (!pq.isEmpty()) {
            String key = pq.maxKey();
            int i = pq.delMax();
            StdOut.println(i + " " + key);
        }
        StdOut.println();

        // reinsert the same strings
        for (int i = 0; i < strings.length; i++) {
            pq.insert(i, strings[i]);
        }

        // delete them in random order
        int[] perm = new int[strings.length];
        for (int i = 0; i < strings.length; i++)
            perm[i] = i;
        StdRandom.shuffle(perm);
        for (int i = 0; i < perm.length; i++) {
            String key = pq.keyOf(perm[i]);
            pq.delete(perm[i]);
            StdOut.println(perm[i] + " " + key);
        }

    }
}

 

 

인덱스 기반 우선순위 큐의 활용

 복수의 정렬된 입력 스트림들을 병합해서 하나의 정렬된 스트림으로 출력하는 작업을 할 수 있다. 공간 (메모리)이 충분하다면 복수의 스트림들을 모두 하나의 배열에 저장한 다음 정렬하면 되지만, 공간이 충분치 않을 때는 인덱스 기반 우선순위 큐를 사용할 수 있다. 공간의 크기에 상관없이 정렬한 다음 출력 가능하기 때문이다.

 먼저 각 스트림을 인덱스와 연관 지어 놓는다. (stream a = 1, b = 2, c = 3,...) 큐에는 각 스트림의 다음 키와 자기 스트림의 인덱스를 부여하여 가지고 있다. (스트림 수가 3개면 큐의 노드 수는 3개) 큐에서 최소항목을 반복적으로 출력 (및 삭제)해나가면서 해당 인덱스(스트림)의 키가 삭제될 때마다 해당 인덱스에 해당하는 스트림의 다음 키를 가져와 큐에 넣는다.

 

1. 정렬된 스트림을 복수 개 받음
2. streams [] : 초기화 작업 (큐에 각 스트림별로 첫 번째 키만 넣어줌)
3. 최소항목 삭제 : 큐에서 최소항목 출력 후 삭제
4. 삽입 : 삭제된 인덱스의 스트림이 비어있지 않으면 다음 키 삽입
5. 3~4 반복

package org.algorithm.sorting;

/*
 * Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne.
 * Last updated: Thu Aug 11 09:07:21 EDT 2022.
 */

import org.algorithm.lib.In;
import org.algorithm.lib.StdOut;

/******************************************************************************
 *  Compilation:  javac Multiway.java
 *  Execution:    java Multiway input1.txt input2.txt input3.txt ...
 *  Dependencies: IndexMinPQ.java In.java StdOut.java
 *  Data files:   https://algs4.cs.princeton.edu/24pq/m1.txt
 *                https://algs4.cs.princeton.edu/24pq/m2.txt
 *                https://algs4.cs.princeton.edu/24pq/m3.txt
 *
 *  Merges together the sorted input stream given as command-line arguments
 *  into a single sorted output stream on standard output.
 *
 *  % more m1.txt
 *  A B C F G I I Z
 *
 *  % more m2.txt
 *  B D H P Q Q
 *
 *  % more m3.txt
 *  A B E F J N
 *
 *  % java Multiway m1.txt m2.txt m3.txt
 *  A A B B B C D E F F G H I I J N P Q Q Z
 *
 ******************************************************************************/

/**
 * The {@code Multiway} class provides a client for reading in several
 * sorted text files and merging them together into a single sorted
 * text stream.
 * This implementation uses a {@link IndexMinPQ} to perform the multiway
 * merge.
 * <p>
 * For additional documentation, see <a href="https://algs4.cs.princeton.edu/24pq">Section 2.4</a>
 * of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */

public class Multiway {

    // This class should not be instantiated.
    private Multiway() {
    }

    // merge together the sorted input streams and write the sorted result to standard output
    private static void merge(In[] streams) {
        int n = streams.length;
        IndexMinPQ<String> pq = new IndexMinPQ<String>(n);
        for (int i = 0; i < n; i++)
            if (!streams[i].isEmpty())
                pq.insert(i, streams[i].readString());

        // Extract and print min and read next from its stream.
        while (!pq.isEmpty()) {
            StdOut.print(pq.minKey() + " ");
            int i = pq.delMin();
            if (!streams[i].isEmpty())
                pq.insert(i, streams[i].readString());
        }
        StdOut.println();
    }


    /**
     * Reads sorted text files specified as command-line arguments;
     * merges them together into a sorted output; and writes
     * the results to standard output.
     * Note: this client does not check that the input files are sorted.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        int n = args.length;
        In[] streams = new In[n];
        for (int i = 0; i < n; i++)
            streams[i] = new In(args[i]);
        merge(streams);
    }
}

---

힙을 이용한 알고리즘 2 : 힙-정렬

우선순위 큐를 활용하여 정렬하는 방법이다. 오름차순으로 정렬하고 싶다면, 먼저 최솟값 우선순위 큐에 모든 항목을 삽입한 뒤 최소항목 삭제를 반복 호출하여 정렬된 순서로 꺼내는 방법이다. 힙 정렬은 크게 다음 2 단계로 구성된다.

• 힙 구성 (heap construction) : 원본 배열 (정렬 대상)을 힙으로 재배치
• 정렬 취합 (sortdown) : 힙에서 항목을 하나씩 꺼내면서 정렬된 결과 생성

 

 힙 정렬은 시, 공간 양쪽에서 모두 최적의 성능을 내는 유일한 알고리즘이다. 최악의 조건에서도 ~2 NlogN의 비교연산, 상수 크기의 추가 공간 사용을 보장한다. 메모리 공간이 제한적인 환경(임베디드, 저가형 모바일 기기)에서는 힙-정렬을 많이 사용한다. 

 반면 현대 시스템에서는 거의 사용되지 않고 있다. 캐시 활용률을 떨어뜨리고, 배열의 인접 항목끼리 비교하는 상황이 드믈어 퀵-정렬, 병합 정렬, 셸정렬에 비해 캐시 미스 확률이 높은 편이다. 반면 우선순위 큐를 구현할 때는 힙이 사용되고 있다. 대용량 데이터 삽입, 최대/최소 값 찾기에서 로그 성능을 보장하기 때문이다.

 

 

힙 구성 (heap construction)

힙-구성 (좌), 정렬 취합 (우)

 배열의 크기가 N일 때 힙을 구성하는 시간은 NlogN이 소요된다. 가장 먼저 배열을 왼쪽부터 순회하며 swim()으로 모든 항목에 걸쳐 현재 배열이 힙-정렬되어있는지 검사한다. (마치 우선순위 큐에서 삽입을 연속으로 진행하듯이)

 조금 더 개선된 방법으로는 배열의 중간 (k/2)부터 순회하면서 sink()로  부분 힙을 생성하는 방식이다. 즉 배열의 모든 항목이 부분 배열의 루트가 되게 하는 방법이다. 만약  어떤 노드의 두 자식 노드가 힙이라면 해당 노드에 sink()를 적용하여 부분 힙을 생성할 수 있다. 

 

정렬 취합

 힙-구성 이후 정렬 취합을 수행한다. 힙-정렬의 대부분 작업이 여기서 소요된다.  힙에 남은 항목 중 최대 항목을 꺼낸 뒤 삭제해 나가면서 힙이 줄어들고 빈 배열의 위치에 꺼낸 항목을 넣는 작업이다. 선택정렬보다 훨씬 적은 수의 비교연산을 수행한다. 힙 순서를 사용해 효율적으로 최대항목을 찾아낼 수 있기 때문이다.

 

알고리즘 개선 : 바닥까지 sink()한 뒤 다시 swim()하기

 항목이 제 위치에 도달했는지 검사하는 작업을 생략할 수는 없을까? 정렬 취합 작업에서 대부분의 항목들이 힙의 바닥에 도달한다. 어차피 바닥에 내려갈 확률이 높으므로 sink()에서 두 자식 중 큰 항목을 위로 올린다. 이렇게 하면 비교 횟수가 점근적으로 2배 줄어든다고 한다. (병합 정렬에 근접하게 됨) 문자열의 길이가 큰 키가 사용되어서 비교연산 비용이 클 때 효과 있다.

package org.algorithm.sorting;

import org.algorithm.lib.StdIn;
import org.algorithm.lib.StdOut;

/*
 * Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne.
 * Last updated: Thu Aug 11 09:07:21 EDT 2022.
 */

/******************************************************************************
 *  Compilation:  javac Heap.java
 *  Execution:    java Heap < input.txt
 *  Dependencies: StdOut.java StdIn.java
 *  Data files:   https://algs4.cs.princeton.edu/24pq/tiny.txt
 *                https://algs4.cs.princeton.edu/24pq/words3.txt
 *
 *  Sorts a sequence of strings from standard input using heapsort.
 *
 *  % more tiny.txt
 *  S O R T E X A M P L E
 *
 *  % java Heap < tiny.txt
 *  A E E L M O P R S T X                 [ one string per line ]
 *
 *  % more words3.txt
 *  bed bug dad yes zoo ... all bad yet
 *
 *  % java Heap < words3.txt
 *  all bad bed bug dad ... yes yet zoo   [ one string per line ]
 *
 ******************************************************************************/

/**
 * The {@code Heap} class provides a static method to sort an array
 * using <em>heapsort</em>.
 * <p>
 * This implementation takes &Theta;(<em>n</em> log <em>n</em>) time
 * to sort any array of length <em>n</em> (assuming comparisons
 * take constant time). It makes at most
 * 2 <em>n</em> log<sub>2</sub> <em>n</em> compares.
 * <p>
 * This sorting algorithm is not stable.
 * It uses &Theta;(1) extra memory (not including the input array).
 * <p>
 * For additional documentation, see
 * <a href="https://algs4.cs.princeton.edu/24pq">Section 2.4</a> of
 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */

public class Heap {

    // This class should not be instantiated.
    private Heap() {
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     *
     * @param pq the array to be sorted
     */
    public static void sort(Comparable[] pq) {
        int n = pq.length;

        // heapify phase
        for (int k = n / 2; k >= 1; k--)
            sink(pq, k, n);

        // sortdown phase
        int k = n;
        while (k > 1) {
            exch(pq, 1, k--);
            sink(pq, 1, k);
        }
    }

    /***************************************************************************
     * Helper functions to restore the heap invariant.
     ***************************************************************************/

    private static void sink(Comparable[] pq, int k, int n) {
        while (2 * k <= n) {
            int j = 2 * k;
            if (j < n && less(pq, j, j + 1)) j++;
            if (!less(pq, k, j)) break;
            exch(pq, k, j);
            k = j;
        }
    }

    /***************************************************************************
     * Helper functions for comparisons and swaps.
     * Indices are "off-by-one" to support 1-based indexing.
     ***************************************************************************/
    private static boolean less(Comparable[] pq, int i, int j) {
        return pq[i - 1].compareTo(pq[j - 1]) < 0;
    }

    private static void exch(Object[] pq, int i, int j) {
        Object swap = pq[i - 1];
        pq[i - 1] = pq[j - 1];
        pq[j - 1] = swap;
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; heapsorts them;
     * and prints them to standard output in ascending order.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        Heap.sort(a);
        show(a);
    }
}