二叉堆

一、介绍

二叉堆是完全二元树或近似完全二元树，二叉堆根据父节点与子节点的大小关系排列方式分为最大堆和最小堆

最大堆：父节点的键值总是大于或等于任何一个子节点的键值

最小堆：父节点的键值总是小于或等于任何一个子节点的键值

image

二、插入数据

image

三、删除数据

image

四、最大堆实现
/**

• Java数据结构之堆
  */
  public class Heap {

  //堆数据结构容器
  private int[] mHeap = null;
  //堆容量
  private int capacity = 10;
  //实际容量
  private int size = 0;

  public Heap() {
  this(10);
  }

  public Heap(int length) {
  this.size = 0;
  this.capacity = length;
  this.mHeap = new int[length];
  }

  /**

  • 最大堆的节点上调算法
  • 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
  • @param start 被上调节点的起始位置
    */
    protected void maxHeapFilterUp(int start) {
    //当前节点的位置
    int current = start;
    //当前节点的父节点的位置
    int parent = (current - 1) / 2;
    //当前节点的值
    int currentHeapValue = mHeap[current];
    while (current > 0) {
    if (mHeap[parent] >= currentHeapValue) {
    break;
    } else {
    mHeap[current] = mHeap[parent];
    current = parent;
    parent = (parent - 1) / 2;
    }
    }
    mHeap[current] = currentHeapValue;
    }

  /**

  • 最大堆的节点下调算法
  • 注：数组实现的堆中，第N个节点的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
  • @param start 被下调节点的起始位置
  • @param end 截至范围
    */
    protected void maxHeapFilterDown(int start, int end) {
    int current = start;
    int left = 2 * current + 1;
    int currentHeapValue = mHeap[current];
    while (left <= end) {
    if (left < end && mHeap[left] < mHeap[left + 1]) {
    left++;
    }
    if (currentHeapValue >= mHeap[left]) {
    break;
    } else {
    mHeap[current] = mHeap[left];
    current = left;
    left = 2 * current + 1;
    }
    }
    mHeap[current] = currentHeapValue;
    }

  /**

  • 获取数据在数组中的索引
  • @param data
  • @return -1 不存在
    */
    protected int getIndex(int data) {
    int i;
    for (i = 0; i < size; i++) {
    if (data == mHeap[i])
    return i;
    }
    return -1;
    }

  /**

  • 插入数据

  • @param data

  • @return -1 表示失败

  • 0 表示成功
    */
    protected int add(int data) {
    if (size == capacity)
    return -1;

    mHeap[size] = data;
    maxHeapFilterUp(size);
    size++;
    return 0;
    }

  /**

  • 删除最大堆中的数据

  • @param data

  • @return -1 删除失败

  • 0 删除成功
    */
    protected int remove(int data) {
    int index;
    if (0 == size)
    return -1;

    index = getIndex(data);
    if (-1 == index)
    return index;

    mHeap[index] = mHeap[--size];
    maxHeapFilterDown(index, size - 1);
    return 0;
    }

  protected void println() {
  System.out.println(Arrays.toString(mHeap));
  }

}