二叉树:堆 博客分类： Tree

    这里说的堆其实是一个完全二叉树,每个节点都不小于自己的子节点,不要跟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;
        }
    }
}