堆.md

堆（Heap）

定义

堆是一个数组，它可以被看作一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素。除了最底层外，该树是完全充满的，而且是从左向右填充。

最大树：在树中，一个结点有子结点，其关键字值都不小于其子结点的关键值。最大堆 是一颗完全二叉树，也是一颗最大树。

最小树：在树中，一个结点有子结点，其关键字值都不大于其子结点的关键值。最小堆 是一颗完全二叉树，也是一颗最小树。

最大堆

插入操作

/**
 * 时间复杂度为O(logn)
 *
 * @param node
 * @param comparable
 * @return
 */
@Override
public boolean insert(Node<T> node, JComparable<T> comparable) {
    if (isFull())
        return false;
    int i = size;
    while ((i != 0) && comparable.moreThan(node.key, elements[i >>> 1].key)) {
        elements[i] = elements[(i - 1) >>> 1];
        i = (i - 1) >>> 1;
    }
    elements[i] = node;
    size++;
    return true;
}

删除操作

/**
 * 删除最大元素（即根结点）
 * 时间复杂度为logn
 *
 * @param comparable
 * @return
 */
@Override
public Node<T> delete(JComparable<T> comparable) {
    if (isEmpty())
        return null;
    Node<T> max = elements[0];    //最大结点
    Node<T> detail = elements[size - 1];    //尾部元素
    int parent = 0, child = 1;  //代表下标
    while (child < size) {
        //取两个子结点中最大的
        if (child < size - 1 &&
                comparable.lessThan(elements[child].key, elements[child + 1].key))
            child++;
        if (comparable.moreOrEquals(detail.key, elements[child].key))
            break;
        //移到低等级
        elements[parent] = elements[child];
        parent = child;
        child = child << 1 + 1;
    }
    elements[parent] = detail;
    size--;
    elements[size] = null;
    return max;
}

最小堆

插入操作

@Override
public boolean insert(Node<T> node, JComparable<T> comparable) {
    if (isFull()) return false;
    int i = size;
    while ((i != 0) && comparable.lessThan(node.key, elements[i >>> 1].key)) {
        elements[i] = elements[(i - 1) >>> 1];
        i = (i - 1) >>> 1;
    }
    elements[i] = node;
    size++;
    return false;
}

删除操作

@Override
public Node<T> delete(JComparable<T> comparable) {
    if (isEmpty())
        return null;
    Node<T> min = elements[0];
    Node<T> detail = elements[size - 1];
    int parent = 0, child = 1;
    while (child < size) {
        if (child < size - 1 &&
                comparable.moreThan(elements[child].key, elements[child + 1].key))
            child++;
        if (comparable.lessOrEquals(detail.key, elements[child].key))
            break;
        elements[parent] = elements[child];
        parent = child;
        child = child << 1 + 1;
    }
    elements[parent] = detail;
    size--;
    elements[size] = null;
    return min;
}