手写数据结构二叉堆

二叉堆又叫优先队列，如果不包含特别结构，我们简称的堆就是指普通二叉堆。

队列我们都知道，是一种先进先出的数据结构，常用于无差别排队场景。但如果有差别排队呢，我的等级比你高，我就优先排于前面。这时候我们就要用到优先队列--堆。

备注：其实我觉得普通队列和堆的选择是有个平衡点的。就比如上面的排队场景，如果偶尔才会有军人来优先排队，使用堆的话就有点不合理(起码我的实现代码不合理，我是根据算法与数据结构里的思想来实现的)，因为军人来了，使用堆会很大几率破坏后面的队形。而我们期望的肯定只是军人放最前面，后面的队形一致。像这种要使用优先场景较少的情况下，又要保持后面的队形不变，使用堆不是最佳选择，还不如普通队列特殊情况处理一下。如果一个场景优先情况很多，包容先进先出的部分错误，使用堆就是个不错选择。

二叉堆的性质：

1.堆是一棵完全二叉树

2.树上的任意节点，它的后裔上的值肯定比这个节点的值要大。

二叉堆的主要操作：

根据性质可知道根上的元素始终是最小元素。所以一般的操作也就是插入元素构建一个堆，然后获取它的最小元素和删除它的最小元素。就像队列一样了，插入，删除(但删除的始终是最小元素)

用java语言实现这个数据结构：

package com.tczs.heap;

import java.util.Arrays;
import java.util.Comparator;

public class BinaryHeap<T> {

    private Object[] array;
    private int capacity = 16;
    private int length;
    private int index;
    private Comparator<? super T> comparator;
    static final int MAXIMUM_CAPACITY = 1 << 30;

    public BinaryHeap(int initialCapacity, Comparator<? super T> comparator){
        this.capacity = initialCapacity;
        this.comparator = comparator;
    }

    public BinaryHeap(int initialCapacity){
        if(initialCapacity > 7)
            this.capacity = initialCapacity;
    }

    public BinaryHeap(Comparator<? super T> comparator){
        this.comparator = comparator;
    }

    public BinaryHeap(){
    }

    public int size(){
        return this.length;
    }

    public T getMin(){
        return get(1);
    }

    public T get(int index){
       return array==null ? null:(T)array[index];
    }

    public void buildHeap(T[] array){
        if(array == null)
            return;
        for(T t : array)
            buildHeap(t);
    }

    public void buildHeap(T element){
        if(array == null)
            array = new Object[capacity];
        if(++index == capacity){
            capacity = Math.min(MAXIMUM_CAPACITY,capacity<<1);
            array = Arrays.copyOf(array,capacity);
        }
        array[index] = element;
        fixedInsertArray();
        length++;
    }

    private void fixedInsertArray(){
        int index = this.index;
        while(index != 1){
            T current = get(index);
            T parent = get(index/2);
            if (compare(current, parent) < 0) {
                array[index / 2] = current;
                array[index] = parent;
            }else
                break;
            index = index/2;
        }
    }

    public T deleteMin(){
        if(array == null)
            return null;
        T result = get(1);
        if(length == 1)
            array[1] = null;
        else if(length == 2){
            array[1] = array[2];
            array[2] = null;
        }else
            deleteM();
        index--;
        length--;
        return result;
    }

    private void deleteM(){
        int index = 1;
        int leftIndex = index<<1;
        T left;
        while((left=get(leftIndex)) != null){
            T right = get(leftIndex+1);
            if(right == null){
                array[index] = left;
                array[leftIndex] = null;
                break;
            }
            if(compare(left,right) < 0){
                array[index] = left;
                array[leftIndex] = null;
            }else {
                array[index] = right;
                leftIndex = leftIndex+1;
                array[leftIndex] = null;
            }
            if(leftIndex<<1 >= capacity || get(leftIndex<<1) == null)
                break;
            index = leftIndex;
            leftIndex = index<<1;
        }
        array[leftIndex] = array[this.index];
        array[this.index] = null;
    }

    private int compare(T current,T parent){
        return comparator==null ? ((Comparable<? super T>)current).compareTo(parent) :
            comparator.compare(current,parent);
    }

}

本文地址：https://blog.csdn.net/fsgsggd/article/details/109268505