java中的堆实现

java中的堆实现

如图：

对于java中的堆，我们使用数组来实现

可以看出，通过一个节点在数组中的索引计算出它的父节点及左右孩子节点的索引。

//返回左节点
public int left(int i) {
    return (i + 1) * 2 - 1;
}
//返回右节点
public int right(int i) {
    return (i + 1) * 2;
}
//返回根节点
public int parent(int i) {
  // i为根结点
    if (i == 0) {
        return -1;
    }
    return (i - 1) / 2;
}

下面是关于堆的一些java算法

大根堆

public void heapify(T[] a, int i, int heapLength) {
        int l = left(i);
        int r = right(i);
        int largest = -1;
        /**
         * 下面两个if条件句用来找到三个元素中的最大元素的位置largest； 
         * l < heapLength说明l在数组内，i非叶子结点；
         */
        if (l < heapLength && a[i].compareTo(a[l]) < 0) {
            largest = l;
        } else {
            largest = i;
        }
        // r < heapLength说明r在数组内
        if (r < heapLength && a[largest].compareTo(a[r]) < 0) {
            largest = r;
        }
        // 如果i处元素不是最大的，就把i处的元素与最大处元素交换，交换会使元素下降
        if (i != largest) {
            T temp = a[i];
            a[i] = a[largest];
            a[largest] = temp;
            // 交换元素后，以a[i]为根的树可能不在满足大根堆性质，于是递归调用该方法
            heapify(a, largest, heapLength);
        }
    }

小根堆

public void heapify(T[] a, int i, int heapLength) {
        int l = left(i);
        int r = right(i);
        int smallest = -1;
        /**
         * 下面两个if条件句用来找到三个元素中的最小元素的位置smallest； 
         * s < heapLength说明l在数组内，i非叶子结点；
         */
        if (l < heapLength && a[i].compareTo(a[l]) > 0) {
            smallest = l;
        } else {
            smallest = i;
        }
        // r < heapLength说明r在数组内
        if (r < heapLength && a[smallest].compareTo(a[r]) > 0) {
            smallest = r;
        }
        // 如果i处元素不是最小的，就把i处的元素与最小处元素交换，交换会使元素下降
        if (i != smallest) {
            T temp = a[i];
            a[i] = a[smallest];
            a[smallest] = temp;
            // 交换元素后，以a[i]为根的树可能不在满足大根堆性质，于是递归调用该方法
            heapify(a, smallest, heapLength);
        }
    }