두 갈래 나무: 더미

여기서 말한 무더기는 사실 완전한 두 갈래 나무로 각 노드는 자신의 하위 노드보다 작지 않으니 jvm의 무더기와 헷갈리지 마라.완전 두 갈래 나무이기 때문에 수조로 구축할 수 있다.수조로 트리를 만드는 규칙은 간단합니다.
한 노드의 부모 노드 아래첨자는 다음과 같습니다. (현재 아래첨자 - 1)/2
한 노드의 왼쪽 노드 아래쪽: 현재 아래쪽* 2 + 1
한 노드의 오른쪽 노드 아래쪽: 현재 아래쪽* 2 + 2
   
수조로 구축할 때 마지막 노드에 쉽게 접근할 수 있기 때문에 우선순위 대기열 같은 응용에 적합하다.매번 노드가 추가될 때마다 항상 먼저 수조의 마지막 빈자리에 삽입한 다음에 순서대로 아버지 노드와 비교하고 아버지 노드가 작으면 교환한다.노드를 삭제할 때마다 뿌리를 삭제하고 되돌려줍니다. 그리고 마지막 노드를 뿌리의 위치에 놓고 비교적 큰 하위 노드와 차례로 비교합니다. 하위 노드보다 크면 교환합니다.
무더기 코드:

import java.util.ArrayList;
import java.util.List;

public class Heap <K,V>{
    private List<Entity<K,V>> heap;
    
    public Heap(){
        heap = new ArrayList<Entity<K,V>>();
    }
    
    public void put(K key,V value){
        Entity<K,V> e = new Entity<K,V>(key, value);
        heap.add(e);
        Comparable<? super K> k = (Comparable<? super K>)key;
        
        int index = heap.size() - 1;
        int parent = (index - 1) / 2;
        
        while(index != parent && k.compareTo(heap.get(parent).key) > 0){
            heap.set(index, heap.get(parent));
            index = parent;
            
            if(index == 0){
                break;
            }
            
            parent = (index -1) / 2;
        }
        
        heap.set(index, e);
    }
    
    public V pop(){
        Entity<K,V> e = heap.get(0);
        
        if(heap.size() == 1){
            heap.remove(0);
        } else {
            Entity<K, V> top = heap.remove(heap.size() - 1);
            heap.set(0, top);

            int left = 1;
            int right = 2;
            int current = 0;

            while (left < heap.size()) {
                int child;
                Comparable<? super K> k = (Comparable<? super K>) heap.get(left).key;

                if (right < heap.size() && k.compareTo(heap.get(right).key) < 0) {
                    child = right;
                } else {
                    child = left;
                }

                k = (Comparable<? super K>) heap.get(current).key;

                if (k.compareTo(heap.get(child).key) < 0) {
                    heap.set(current, heap.get(child));
                    heap.set(child, top);
                    current = child;
                    left = current * 2 + 1;
                    right = left + 1;
                } else {
                    break;
                }
            }
        }
        
        return e.value;
    }
    
    public int size(){
        return heap.size();
    }
    
    public boolean isEmpty(){
        return heap.isEmpty();
    }
    
    private static final class Entity <K,V>{
        private K key;
        private V value;
        
        public Entity(K key,V value){
            this.key = key;
            this.value = value;
        }
    }
}