BinaryHeap (最小堆)

￡神魔★判官ぃ 2022-06-03 10:36 117阅读 0赞

package heap;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 二叉堆(最小堆)
     * Created by long.chen  on 2017/12/25.
     */
    public class BinaryHeapMin<T extends Comparable<T>> {
    
        private List<T> heap;
    
        public BinaryHeapMin() {
            this.heap = new ArrayList<>();
        }
    
        /**
         * 向下调整
         *
         * @param start
         * @param end
         */
        public void fliterdown(int start, int end) {
            int left = 2 * start + 1;
            T temp = heap.get(start);
            while (left <= end) {
                int tempSec = heap.get(left).compareTo(heap.get(left + 1));
                if (left < end && tempSec > 0)
                    left++;
                tempSec = temp.compareTo(heap.get(left));
                if (tempSec <= 0)
                    break;
                else {
                    heap.set(start, heap.get(left));
                    start = left;
                    left = 2 * left + 1;
                }
            }
            heap.set(start, temp);
        }
    
        /**
         * 删除
         *
         * @param data
         * @return
         */
        public int delete(int data) {
            if (heap.isEmpty())
                return -1;
            int index = heap.indexOf(data);
            if (index == -1)
                return -1;
            heap.set(index, heap.get(heap.size() - 1));
            heap.remove(heap.size() - 1);
            if (heap.size() > 1)
                fliterdown(index, heap.size() - 1);
            return 0;
        }
    
        /**
         * 向上调整
         * @param end
         */
        public void fliterup(int end){
            int parent=(end-1)/2;
            T temp = heap.get(end);
            while (end > 0){
                int tempSec = heap.get(parent).compareTo(temp);
                if (tempSec <= 0)
                   break;
                else {
                    heap.set(end,heap.get(parent));
                    end=parent;
                    parent=(parent-1)/2;
                }
            }
            heap.set(end,temp);
        }
        public void insert(T data){
            heap.add(data);
            fliterup(heap.size()-1);
        }
        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < heap.size(); i++)
                sb.append(heap.get(i) + " ");
            return sb.toString();
        }
    
        public static void main(String[] args) {
            int arr[] = {80, 40, 30, 60, 90, 70, 10, 50, 20};
            BinaryHeapMin<Integer> heap = new BinaryHeapMin<>();
            System.out.println("开始添加");
            for (int i = 0; i < arr.length; i++) {
                heap.insert(arr[i]);
            }
            System.out.printf("\n== 最 小 堆: %s", heap);
            int insertData = 85;
            heap.insert(insertData);
            System.out.printf("\n== 最 小 堆: %s", heap);
            heap.delete(arr[3]);
            System.out.printf("\n== 最 小 堆: %s", heap);
        }
    }