Java利用完全二叉树创建大根堆和小根堆

下面是详细讲解“Java利用完全二叉树创建大根堆和小根堆”的完整攻略。

创建大根堆和小根堆的概念

在创建堆的时候，需要将输入的数据元素想象成一颗完全二叉树。然后将这个完全二叉树转换为堆，转换之后的堆即为大根堆或小根堆。

大根堆：每个节点的值都大于或等于它的子节点值。

小根堆：每个节点的值都小于或等于它的子节点值。

创建大根堆和小根堆的步骤

1. 将输入的元素插入到一个空的堆中，使之成为一个没有排序的堆，这时候堆顶元素为第一个被插入的元素。
2. 从堆顶开始，对完全二叉树进行遍历。从当前节点向下一级移动时，找到其左右子节点中比当前节点值大/小的那个节点，与当前节点交换位置。
3. 重复步骤2，直到所有的元素遍历完毕，此时堆顶元素即为最大值/最小值。

Java实现大根堆和小根堆的代码示例

下面给出两个代码示例，分别实现了大根堆和小根堆的创建过程。

大根堆示例代码

public void bigHeap(int[] data){
    for(int i=0;i<data.length;i++){
        int j=i;
        while(j>0){
            if(data[j]>data[(j-1)/2]){
                int tmp=data[(j-1)/2];
                data[(j-1)/2]=data[j];
                data[j]=tmp;
                j=(j-1)/2;
            }else{
                break;
            }
        }
    }
}

其中，data为输入的元素数组，代码中将其视为一颗完全二叉树，从树的底部开始往上遍历，每次比较当前节点与其父节点值的大小，如果当前节点值大于父节点，则交换位置，继续向上比较，否则停止。

小根堆示例代码

public void smallHeap(int[] data){
    for(int i = 0; i < data.length; i++){
        int j = i;
        while(j > 0){
            if(data[j] < data[(j-1)/2]){
                int tmp = data[(j-1)/2];
                data[(j-1)/2] = data[j];
                data[j] = tmp;
                j = (j-1)/2;
            } else{
                break;
            }
        }
    }
}

与大根堆的创建过程类似，此处将比较大小操作改为了当前节点小于父节点时交换位置。