欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树:堆 博客分类: Tree  

程序员文章站 2024-02-04 16:47:28
...
    这里说的堆其实是一个完全二叉树,每个节点都不小于自己的子节点,不要跟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;
        }
    }
}