더미 (우선순위 대기열)

1 두 갈래 나무의 순서 저장: 수조를 사용하여 두 갈래 나무 구조를 저장하고 두 갈래 나무를 층순으로 훑어보는 방식으로 수조에 넣는다.이런 방식은 일반적으로 완전한 두 갈래 나무에만 적용되는데, 일반적인 두 갈래 나무는 공간 낭비가 비교적 심각하게 될 것이다.두 무더기(heap)는 논리적으로 완전한 두 갈래 나무로 물리적으로 수조에 저장된다.(1) 임의의 결점을 만족시키는 값은 그 하위 나무의 결점 값보다 크다.무더기(최대더미)라고 하고, 반대로 작은 무더기(최소더미)라고 한다.(2)무더기의 작용: 집합 중의 최치를 신속하게 찾습니다.3더미 중 원소 하표 관계: 양친(parent)의 하표, 또는 좌우 아이(child)의 하표를 알았을 때: (1) 루트 노드 하표가 0에서 계산을 시작할 때 왼쪽 아이(left)의 하표= 2× parent + 1, 오른쪽 아이 (right) 아래 표시= 2× parent + 2. 양친하표(좌우자수 구분하지 않음) = (child-1)/2;(2) 루트 노드 아래 첨자가 1부터 계산할 때 왼쪽 아이(left) 아래 첨자 = 2× parent, 오른쪽 아이 (right) 아래 표시 = 2× parent + 1. 양친 아래 표시(좌우 트리 구분하지 않음) =child/2;4 아래로 조정: (주의) 전제는 좌우 나무가 이미 한 무더기가 되어야 조정할 수 있다는 것이다.(1)size를 통해array에서 어떤 원소가 유효한 퇴적원소, 즉 유효원소 개수를 지정합니다.(2) index는 어느 위치의 하단에서부터 조정할 것인지를 나타낸다.(3) 여기는 작은 무더기를 예로 들면 뿌리 노드 아래에 0을 표시하는 조정이다.

 public static void shiftDown(int[] array, int size, int index) {
        int parent = index;
        int child = 2 * parent + 1;  //   parent  
        while (child < size) {
            //  ,  
            if (child + 1 < size && array[child + 1] < array[child]) {
                child = child + 1;
            }
            if (array[child] < array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
            } else {
                break;
            }
            //   parent   child,  .
            parent = child;
            child = 2 * parent + 1;
        }
    }

무더기의 하향 조정 과정:

public static void shiftDown(int[] array, int size, int index) {
        int parent = index;
        int child = 2 * parent + 1;
        while (child < size) {
            if (child + 1 < size && array[child + 1] > array[child]) {
                child = child + 1;
            }
            if (array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;
            } else {
                break;
            }
            parent = child;
            child = 2 * parent + 1;
        }
    }

4 쌓기: 무질서한 수조를 쌓으면 아래로 조정할 수도 있고 위로 조정할 수도 있다.일반적으로 아래로 조정한다.쌓는 과정은 마지막 비잎결점을 찾아 아래로 조정하기 시작하고 뒤에서 앞으로 수조를 옮겨야 한다.시간 복잡도(OlogN)는 아래쪽으로 스몰오버를 조정하는 경우입니다.

// : , , i--
    public static void createHeap(int[] array, int size) {
        for (int i = (size - 1 - 1) / 2; i >= 0; i--) {
            shiftDown(array, size, i);
        }
    }
    public static void main(String[] args) {
        int[] array = {9,5,2,7,3,6,8};
        createHeap(array, array.length);
        System.out.println(Arrays.toString(array));
    }
    // : [2, 3, 6, 7, 5, 9, 8]

5 상향 조정이라면 뿌리 노드가 바짝 붙어 있는 첫 번째 양친 노드를 시작 위치로 찾아 이동 후 수조를 반복한다.6 구축 더미의 응용: 우선순위 대기열(PriorityQueue)(이것은 하나의 대기열이고 모두 대기열과 관련된 성질임을 주의): 우선순위 상황에 따라 처리 대상을 처리해야 한다. 예를 들어 우선순위가 가장 높은 대상을 먼저 처리한 다음에 우선순위가 높은 대상을 처리해야 한다.작업 -----입력 대기열 (무더기로 예를 들면): (1) 먼저 꼬리에 꽂는 방식으로 그룹을 넣습니다.(2) 양친과의 값의 크기를 비교하고 양친의 값이 크면 무더기의 성질을 만족시켜 끝(3)을 삽입하지 않으면 양친과의 위치의 값을 교환하고 뿌리가 끝날 때까지 2, 3단계를 다시 진행한다.

private static void shiftUp(int[] array, int index) {
        int child = index;
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (array[parent] < array[child]) {
                int tmp = array[parent];
                array[parent] = array[child];
                array[child] = tmp;
            } else {
                //  .  
                break;
            }
            child = parent;
            parent = (child - 1) / 2;
        }
    }

작업 ----- 대기열 출력 (우선순위가 가장 높음) (무더기로 예를 들면): (1) 아래에 0으로 표시된 요소가 바로 팀의 첫 번째 요소입니다.삭제하는 동시에, 우리도 남은 구조가 여전히 한 무더기가 되기를 바란다.(2) 사실상 마지막 요소로 팀의 첫 번째 요소를 대체한 다음에 마지막 요소를 삭제하고 아래로 조정합니다.

 public int poll() {
        int oldValue = array[0];
        array[0] = array[size - 1];
        size--;
        shiftDown(array, size, 0);
        return oldValue;
    }

조작-----취대 첫 원소(우선순위가 가장 높음)(대더미를 예로 들면): 더미 원소로 돌아가면 됩니다.

public int peek() {
        return array[0];
    }

7 TopK 문제.