우선순위 대기열: 무더기 무더기 코드 및 응용.

두 갈래 나무의 순서 저장

수조를 사용하여 두 갈래 나무를 보존하는 것은 두 갈래 나무를 층순으로 훑어보는 방식으로 수조에 보존하는 것이다. 이런 방식은 일반적으로 완전한 두 갈래 나무를 나타내는 데 쓰인다.

무더기가 뭐예요?

1. 더미는 완전히 두 갈래 나무이다. 2. 수조에 저장된 3. 큰 뿌리 더미 즉 임의의 결점의 값은 모두 그 자수에 있는 결점의 값보다 크고 큰 무더기 또는 최대 더미라고 한다. 4, 작은 뿌리 더미는 큰 뿌리 더미와 반대로 작은 무더기라고도 하고 가장 작은 무더기라고도 한다.5. 더미는 일반적으로 집합 중의 가장 높은 값을 신속하게 찾는 데 쓰인다.쌓인 코드에 대한 구현:

/**
 * @ClassName TestHeap
 * @Description TODO
 * @Author  
 * @Date 2019/11/2522:21
 * @Version1.0
 **/
public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap(){
        this.elem = new int[20];
        this.usedSize = 0;
    }
    public void adjustDown(int root ,int len){
        int parent = root;
        int child = 2*parent+1;
        while(child<len){
            if(child+1<len&&elem[child]<elem[child+1]){
                child = child+1;
            }
            if(elem[child]>elem[parent]){
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent+1;
            }else{
                break;
            }
        }
    }
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
        for (int i = (this.usedSize-1-1)/2; i >= 0; i--) {
            adjustDown(i,this.usedSize);
        }
    }
    public void adjustUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if(this.elem[child] > this.elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;
                parent = (child-1)/2;
            }else {
                break;
            }
        }
    }
    public boolean isFull(){
        return this.usedSize == this.elem.length;
    }
    public void pushHeap(int val) {
        if(isFull()) {
            this.elem = Arrays.copyOf
                    (this.elem,this.elem.length*2);
        }
        this.elem[this.usedSize] = val;
        this.usedSize++;//11
        adjustUp(usedSize-1);
    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }
    public void popHeap() {
        //0、   
        if(isEmpty()) {
            return;
        }
        //1、 
        int tmp = this.elem[0];
        this.elem[0] = this.elem[this.usedSize-1];
        this.elem[this.usedSize-1] = tmp;
        this.usedSize--;
        //2、 ， 0 
        adjustDown(0,this.usedSize);
    }
    public int getPop() {
        if(isEmpty()) {
            return -1;
        }
        return this.elem[0];
    }

    public void display() {
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] +" ");
        }
        System.out.println();
    }
    public void heapSort(){
        int end = usedSize-1;
        //LinkedList list = new LinkedList<>();
        while(end>0){
            int tmp = this.elem[0];
            this.elem[0] = this.elem[end];
            this.elem[end] = tmp;
            //list.addFirst(this.elem[end]);
            adjustDown(0,end);
            end--;
        }
        //return list;
    }
}

TOP-K 문제

더미로 TOP-K 문제를 해결할 때 앞의 K 개의 최대치를 찾아야 할 때: K 길이의 작은 뿌리 더미를 만들고 집합 중의 모든 원소를 두루 훑어보고 더미 원소와 비교한다. 만약에 더미 원소보다 크면 넣고 아래로 조정한다. 다시 한 번 작은 뿌리 더미로 조정한다. 집합을 두루 훑어본 후에 작은 뿌리 더미의 원소는 앞의 K 개의 가장 큰 원소다.반대로 앞의 K개의 최소 원소를 찾으려면 큰 루트를 만들어서 해결해야 한다.