数据结构--堆（完全二叉树，线性表实现）

heap 堆

堆其实就是一种特殊的队列——优先队列。

1. 堆序性 (heap order): 任意节点都优于它的所有孩子。

   a. 如果是任意节点都大于它的所有孩子，这样的堆叫大顶堆，Max Heap;

   b. 如果是任意节点都小于它的所有孩子，这样的堆叫小顶堆，Min Heap;

大顶堆 节点 右 元素 优先于 左元素

用 ArrayList 来 实现 堆 ， 完全二叉树

父节点 (i - 1) / 2

子节点 左： 2 * i + 1 右：2 * i + 2

添加

public void add(E element) {
       list.add(element);
       int i = size;
       size++;
       while (((i - 1) / 2) > -1 && c.compare(element, list.get((i - 1) / 2)) > 0)
       {
           //有父节点并且大于父节点 交换
           swap((i - 1) / 2, i);
           i = (i - 1) / 2;
       }
   }

删除

public E remove() {
        E first = list.get(0);
        size--;
        int i = size;
        list.set(0, list.get(i));
        list.remove(i);
        i = 0;
        while (2 * i + 1 < size)
        {
            //有子节点并且小于子节点     与较大子节点 交换

            //两个节点 第二个大
            if (2 * i + 2 < size && c.compare(list.get(2 * i + 2), list.get(2 * i + 1)) > 0)
            {

                if (c.compare(list.get(i), list.get(2 * i + 2)) < 0)
                {
                    swap(i, 2 * i + 2);
                    i = 2 * i + 2;
                }
                else break;
            }
            else//第一个大
            {
                if (c.compare(list.get(i), list.get(2 * i + 1)) < 0)
                {
                    swap(i, 2 * i + 1);
                    i = 2 * i + 1;
                }
                else break;
            }
        }
        return first;
    }

完整类

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

public class Heap<E> {

    private ArrayList<E> list = new ArrayList<E>();
    private Comparator<E> c = null;

    public Heap(Comparator<E> c) {
        this.c = c;
    }

    public int getSize() {
        return size;
    }

    private int size = 0;

    public Heap() {
        c = (e1, e2) -> ((Comparable<E>) e1).compareTo(e2);
    }

    public Heap(E[] arr, Comparator<E> c) {
        this.c = c;
        for (E e : arr) add(e);
    }

    public Heap(E[] arr) {
        if (c == null) c = (e1, e2) -> ((Comparable<E>) e1).compareTo(e2);
        for (E e : arr) add(e);
    }

    private void swap(int index1, int index2) {
        E temp = list.get(index1);
        list.set(index1, list.get(index2));
        list.set(index2, temp);
    }

    public void add(E element) {
        list.add(element);
        int i = size;
        size++;
        while (((i - 1) / 2) > -1 && c.compare(element, list.get((i - 1) / 2)) > 0)
        {
            //有父节点并且大于父节点 交换
            swap((i - 1) / 2, i);
            i = (i - 1) / 2;
        }
    }

    public E remove() {
        E first = list.get(0);
        size--;
        int i = size;
        list.set(0, list.get(i));
        list.remove(i);
        i = 0;
        while (2 * i + 1 < size)
        {
            //有子节点并且小于子节点     与较大子节点 交换

            //两个节点 第二个大
            if (2 * i + 2 < size && c.compare(list.get(2 * i + 2), list.get(2 * i + 1)) > 0)
            {

                if (c.compare(list.get(i), list.get(2 * i + 2)) < 0)
                {
                    swap(i, 2 * i + 2);
                    i = 2 * i + 2;
                }
                else break;
            }
            else//第一个大
            {
                if (c.compare(list.get(i), list.get(2 * i + 1)) < 0)
                {
                    swap(i, 2 * i + 1);
                    i = 2 * i + 1;
                }
                else break;
            }
        }
        return first;
    }

    @Override
    public String toString() {
        return "heap{   size=" + size + "   list=\n" + list + "\n}";
    }
}