堆

1. 数据结构介绍

要求实现一种堆数据结构，具有如下操作：

1. 可以动态添加元素
2. 可以修改给定元素
3. 可以动态删除元素，可以删除指定位置的元素，以及删除给定的元素
4. 获取堆顶元素
5. 弹出堆顶
6. 获取堆中的元素个数
7. 用户可以指定比较策略

2. 算法

• 对于可以动态增删元素，可以使用动态数组ArrayList来实现；
• 如果需要对给定的元素进行操作，我们需要知道这个元素在堆数组中的下标，因此需要一个查找表记录每一个元素及其在堆数组中的下标；
• 对于修改元素，我们只需要将修改后的元素同时做一次heapInsert和heapify即可，因为修改后，元素的排序指标可能变大也可能变小，或者不变，因此heapInsert和heapify最多只会发生一个；这个叫做元素的resign（重新分配）
• 对于删除元素，我们只需要把最后一个元素last和被删除的元素交换，堆的大小减少1，然后resign这个last元素，如果被删除的刚好是最后一个，直接删除即可。
• 可以使用比较器让比较策略灵活指定。

3. 代码

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;

public class EnhancedHeap<T> {

    private ArrayList<T> arrayList;

    private HashMap<T,Integer> indexMap;

    private Comparator<T> comparator;

    private int size;

    public EnhancedHeap(Comparator<T> comparator){
        this.comparator = comparator;
        arrayList = new ArrayList<>();
        indexMap = new HashMap<>();
    }

    public int size(){
        return size;
    }

    public void add(T data){
        arrayList.add(data);
        indexMap.put(data,size);
        heapInsert(size++);
    }

    public void remove(T data){
        Integer index = indexMap.get(data);
        if(index != null){
            if(index == size -1){
                arrayList.remove(--size);
            }else{
                swap(arrayList.get(index),arrayList.get(--size));
                arrayList.remove(size);
                resign(index);
            }
            indexMap.remove(data);
        }
    }

    public void update(T data){
        Integer index = indexMap.get(data);
        if (index != null)resign(index);
    }

    public T poll(){
         T ret  = arrayList.get(0);
         swap(ret,arrayList.get(size - 1));
         arrayList.remove(--size);
         heapify(0);
         indexMap.remove(ret);
         return ret;
    }

    public T peek(){
        return arrayList.get(0);
    }

    private void resign(int index){
        heapInsert(index);
        heapify(index);
    }

    private void heapInsert(int index){
        int parent;
        while(comparator.compare(arrayList.get(index),arrayList.get(parent = (index-1) / 2 )) > 0){
            swap(arrayList.get(index), arrayList.get(parent));
            index = parent;
        }
    }

    private void heapify(int index){
        int child, bound = size >> 1;
        while(index < bound){
            child = (index << 1) | 1;
            if(child + 1 < size && comparator.compare(arrayList.get(child),arrayList.get(child+1)) < 0) ++child;
            if(comparator.compare(arrayList.get(index),arrayList.get(child)) < 0){
                swap(arrayList.get(index),arrayList.get(child));
                index = child;
            }else return;
        }
    }

    private void swap(T t1, T t2){
        Integer index1 = indexMap.get(t1), index2 = indexMap.get(t2);
        arrayList.set(index1,t2);
        arrayList.set(index2,t1);
        indexMap.put(t1,index2);
        indexMap.put(t2,index1);
    }

    public static void main(String[] args) {
        // 测试程序
        EnhancedHeap<Info> enhancedHeap = new EnhancedHeap<>((a,b)-> a.value - b.value);
        Info a = new Info(1), b = new Info(2), c = new Info(3);
        enhancedHeap.add(a);
        System.out.println("size: "+enhancedHeap.size+"  top: "+enhancedHeap.peek());
        enhancedHeap.add(b);
        System.out.println("size: "+enhancedHeap.size+"  top: "+enhancedHeap.peek());
        enhancedHeap.add(c);
        System.out.println("size: "+enhancedHeap.size+"  top: "+enhancedHeap.peek());
        c.value = 7;
        enhancedHeap.update(c);
        System.out.println("size: "+enhancedHeap.size+"  top: "+enhancedHeap.peek());
        enhancedHeap.remove(a);
        System.out.println("size: "+enhancedHeap.size+"  top: "+enhancedHeap.peek());
        System.out.println("top: "+enhancedHeap.poll());
        System.out.println("size: "+enhancedHeap.size+"  top: "+enhancedHeap.peek());
        enhancedHeap.add(new Info(8));
        System.out.println("size: "+enhancedHeap.size+"  top: "+enhancedHeap.peek());
    }

    public static class Info{
        int value;
        public Info(int v){
            value = v;
        }

        @Override
        public String toString() {
            return value+"";
        }
    }
}