JDK에서 우선순위 큐가 어떻게 구현되는지에 대한 자세한 설명

이 글에서는 주로 JDK 소스코드의 PriorityQueue를 자세하게 소개하고 있는데, 관심 있는 친구들은 참고해 보세요

1. 우선순위 큐의 적용

우선순위 큐는 프로그램 개발에서 일반적입니다. 예를 들어 운영 체제가 프로세스를 예약할 때 실행 가능한 알고리즘은 새 프로세스가 포크()되면 먼저 큐에 배치됩니다. 운영 체제 내부의 스케줄러는 실행을 위해 우선순위 큐에서 우선순위가 높은 프로세스를 지속적으로 꺼내는 일을 담당합니다. 크롤러 시스템은 실행 중에 우선순위 큐 루프에서 우선순위가 높은 프로세스를 가져와야 하는 경우도 많습니다. 레벨 작업 및 캡처. 이와 같은 작업을 우선순위에 따라 나누지 않으면 시스템이 필연적으로 실패할 수 있습니다. 예를 들어 운영 체제에서는 우선순위가 낮은 프로세스가 계속해서 리소스를 점유하고 우선순위가 높은 프로세스는 항상 대기열에서 대기합니다. 또한 우선순위 큐에는 그리디 알고리즘에도 일부 응용 프로그램이 있습니다.

2. 우선순위 큐 구현 원리

우선순위 큐 구현은 바이너리 힙 구조를 사용하며, 다음 두 가지 속성(Heap 속성)을 만족해야 합니다. , 여기에 작은 상단 힙을 예로 들어 설명합니다.

1. 모든 노드의 값은 해당 하위 노드의 값보다 작거나 같습니다.
2. 모든 노드는 위에서 아래로, 왼쪽에서 오른쪽으로 채워져 완전한 이진 트리가 됩니다.

이 두 가지 규칙을 바탕으로 바이너리 힙 구현 시 배열을 사용하는 경우가 많습니다. JDK에서 바이너리 힙(우선순위 큐) 구현을 살펴보겠습니다.

3. JDK에서 우선순위 큐가 구현되는 방식

소스 코드를 연구하는 가장 좋은 방법은 디버그하고 변수의 변경 사항을 확인하는 것입니다. 각 단계에서 간단하게 데모를 작성하고 소스 코드를 디버그하여 알아낼 수 있습니다.

여기서는 우선 순위 대기열을 만들고 여기에 세 가지 요소를 추가합니다. Eclipse 편집기를 사용하는 경우 F5를 눌러 소스 코드를 입력할 수 있습니다.

여기에서 코드가 실행되면 PriorityQueue는 자체 오버로드된 생성자 중 하나를 호출합니다. 첫 번째 매개변수는 배열의 기본 크기이고 두 번째 매개변수는 요소 비교를 위한 비교기입니다. 우선순위 큐를 사용할 때 자신만의 비교기를 구현하도록 선택할 수 있습니다.

 public PriorityQueue(int initialCapacity,
             Comparator<? super E> comparator) {
    // Note: This restriction of at least one is not actually needed,
    // but continues for 1.5 compatibility
    if (initialCapacity < 1)
      throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
  }

다음으로 요소 추가 시 Offer 작업을 살펴보겠습니다.

 public boolean offer(E e) {
    if (e == null)
      throw new NullPointerException();
    //记录了队列被修改的次数
    modCount++;
    int i = size;
    if (i >= queue.length)
      //扩容
      grow(i + 1);
    //增加元素个数
    size = i + 1;
    if (i == 0) 
      //第一次添加元素，直接放到第0个位置即可
      queue[0] = e;
    else
      //需要将元素放到最后，再做上滤操作
      siftUp(i, e);
    return true;
  }

한 줄씩 설명하겠습니다. 먼저 Offer 메서드는 매개변수가 비어 있지 않은지 확인합니다. 그러면 modCount 변수가 자동으로 수정됩니다. modCount는 큐가 수정된 횟수를 기록합니다. 그런 다음 배열이 범위를 벗어나는지 여부를 결정합니다. 다음으로 요소를 추가합니다. . 현재 요소가 0이면 해당 요소를 배열의 첫 번째 위치에 직접 배치하고, 그렇지 않으면 siftUp 작업을 수행합니다.

 private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // Double size if small; else grow by 50%
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                     (oldCapacity + 2) :
                     (oldCapacity >> 1));
    // overflow-conscious code
    if (newCapacity - MAX_ARRAY_SIZE > 0)
      newCapacity = hugeCapacity(minCapacity);
    //元素拷贝
    queue = Arrays.copyOf(queue, newCapacity);

위 코드는 대기열을 확장합니다. 소스 코드의 주석 도 매우 명확합니다. 먼저 현재 배열 크기가 충분히 작은지 확인합니다(<64). 충분히 작으면 크기를 2배로 늘리고, 그렇지 않으면 원래 크기에 50%를 추가합니다. 마지막으로 여기에서 크기가 오버플로되는지 여부에 대한 판단이 이루어진다는 점에 유의해야 합니다.

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
      throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
      Integer.MAX_VALUE :
      MAX_ARRAY_SIZE;
  }

확장해야 할 크기가 이미 <0인 경우 분명히 오버플로가 발생한 것이며 여기에 OutOfMemory 예외가 발생합니다.

private void siftUpUsingComparator(int k, E x) {
    while (k > 0) {
      //计算父亲节点的下标
      int parent = (k - 1) >>> 1;
      Object e = queue[parent];
      //与父节点进行比较
      if (comparator.compare(x, (E) e) >= 0)
        break;
      queue[k] = e;
      k = parent;
    }
    queue[k] = x;
  }

우선순위 대기열 속성 1을 보장하려면 각 요소를 삽입할 때 노드의 상위 요소와 비교하여 올바른 위치를 찾아야 합니다. 일부 데이터 구조 책에서는 이 작업을 퍼콜레이트(percolate)라고 합니다. 위로).

큐에 넣기 작업이 완료되었습니다. 다음은 대기열에서 빼기 작업, 즉 poll() 작업입니다.

public E poll() {
    if (size == 0)
      return null;
    int s = --size;
    //自增变量，代表队列修改次数
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
      siftDown(0, x);
    return result;
  }

이 메서드는 먼저 배열의 첫 번째 요소를 결과로 가져옵니다. 힙의 상단이 항상 가장 작은 요소인 경우) 대기열의 마지막 요소를 첫 번째 위치에 놓고 마지막으로 siftDown을 사용하여 대기열의 속성을 보장하기 위해 몇 가지 조정을 수행합니다. 퍼콜레이트 다운(percolate down)이라고 부른다.

 private void siftDownUsingComparator(int k, E x) {
 

    int half = size >>> 1;
    //这里k必须有孩子，故叶节点需要比较
    while (k < half) {
      //以下几行代码到较小的那个儿子,用变量c表示
      int child = (k << 1) + 1;
      //这里假设左儿子比较小
      Object c = queue[child];
      int right = child + 1;
      //左右儿子比较，如果右儿子小则将c赋值为右儿子
      if (right < size &&
        comparator.compare((E) c, (E) queue[right]) > 0)
        c = queue[child = right];
      //如果x比小儿子还小，说明k就是正确位置
      if (comparator.compare(x, (E) c) <= 0)
        break;
      queue[k] = c;
      k = child;
    }
    queue[k] = x;
  }

위 그림에서 볼 수 있듯이 k는 하향 필터링 과정에서 아들과 지속적으로 비교되며 우선순위 큐의 순서가 충족되면 루프가 끊어집니다.

[관련 추천]

1. Java 무료 동영상 튜토리얼

Java 주석 종합 분석

3. FastJson 튜토리얼 매뉴얼

위 내용은 JDK에서 우선순위 큐가 어떻게 구현되는지에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!