Java数据结构之堆怎么建立

堆的性质

堆逻辑上是一棵完全二叉树，堆物理上是保存在数组中 。

总结：一颗完全二叉树以层序遍历方式放入数组中存储，这种方式的主要用法就是堆的表示。

并且 如果已知父亲(parent) 的下标，

则： 左孩子(left) 下标 = 2 * parent + 1;

右孩子(right) 下标 = 2 * parent + 2;

已知孩子（不区分左右）(child)下标，则：

双亲(parent) 下标 = (child - 1) / 2;

堆的分类

大堆：根节点大于左右两个子节点的完全二叉树 （父亲节点大于其子节点），叫做大堆，或者大根堆，或者最大堆 。

小堆：根节点小于左右两个子节点的完全二叉树叫 小堆（父亲节点小于其子节点），或者小根堆，或者最小堆。

堆的向下调整

现在有一个数组，逻辑上是完全二叉树，我们通过从根节点开始的向下调整算法可以把它调整成一个小堆或者大堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

以小堆为例：

1、先让左右孩子结点比较，取最小值。

2、用较小的那个孩子结点与父亲节点比较，如果孩子结点2337c6680630eee072bbc8c21289626f大根堆

代码示例：

  public void heapSort(){
        int end=useSize-1;
        while(end>0){
            int tmp=elem[0];
            elem[0]=elem[end];
            elem[end]=tmp;
            shiftDown(0,end);//假设这里向下调整为大根堆
            end--;
        }
    }

以上是Java数据结构之堆怎么建立的详细内容。更多信息请关注PHP中文网其他相关文章！