【数据结构】大根堆和小根堆

椰椰椰耶

发布于 2024-10-15 15:24:04

14100

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

大根堆实现逻辑

从整棵树的最后一颗子树开始调整，每次都让根节点和左右孩子去比较，如果根节点比左右孩子的最大值要小，那么就将这两个值进行交换，然后此时这颗子树变成了大根堆，再看下一颗树

然后对下一颗树进行相同的处理方法，后面的子树依次交换：

当每棵子树都是大根堆的情况下，那么这棵树也就是大根堆了

每一次交换的步骤为：

从最后一棵树开始调整
左右孩子的最大值和根节点进行比较，如果大于根节点，就交换

遇到的主要问题

第一组根节点和左孩子节点的值在哪

既然调整要从最后一棵子树的根节点开始，那如何确定最后一棵子树的根节点在哪？

把最后一棵子树的根节点记作 p(parent)，左节点的值记作 c(child)
由于堆是由数组实现的，我们最初在创建堆的时候，每一个值都有一个下标，并且是按照层序排序的方式进行完全二叉树的构建，所以原数组的最后一个元素，也就是下标为数组长度-1 (len - 1) 的元素就是最后一个叶子节点，既然知道了最后一棵子树根节点的左孩子节点，那么就可以推出根节点的位置了，p 的下标为：(len-1-1)/2

后续根节点和左孩子节点的值如何确定

最后一棵子树的根节点和孩子找到了，并且交换完成了，那怎么确定下一棵子树中要交换的一组根节点和左孩子节点的值呢？

之后的根节点 p 只需要在每一交换完成之后进行 p-- 的操作就可以定位到下一棵需要交换的子树的根节点位置了，最后一个 p 的下标为 0。
而孩子节点 c 则需要通过根节点的位置进行推导，c 的下标为：2*p+1

右孩子值更大怎么办

把左孩子节点记作 c(child)，每次都是 c(child) 与根节点 p(parent) 进行交换，那要是右孩子节点比左孩子节点要大呢？

因为我们每次都是对左右孩子的最大值与根节点进行交换，所以我们要时刻保证 c(child) 代表的是左右孩子中更大的那个。由于 c(child) 最先是指向左孩子的，

若左孩子节点 > 右孩子节点，继续进行交换
若左孩子节点 < 右孩子结点，则 child++，让 child 代表右孩子

这一切都是发生在每一次准备进行交换的前一刻，为将要交换的 child 和 parent 提供准确的数据

什么时候一轮交换结束

在每一次进行交换操作的时候，什么时候代表交换结束呢？

如何进行交换操作

需要交换的元素知道了，交换开始的条件知道了，交换的结束条件也知道了，那该如何进行交换操作呢？

此时我们创建一个 swap(int i, int j) 交换方法：

创建一个 tmp 整型变量，用来存放 elem[i] 的值
再将 elem[i] 的值赋给 elem[i]
最后将 tmp 中存放的 elem[i] 的值赋给 elem[j]

大根堆完整代码

public void creatHeap(){  
    for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {  
        shiftDown2(parent,usedSize);  
    }
}  
  
public void swap(int i, int j) {  
    int tmp = elem[i];  
    elem[i] = elem[j];  
    elem[j] = tmp;  
}  
  
  
public void shiftDown(int parent, int end) {  
    //parent的值是作为参数传进来的，我们需要用parent的下标算出child的下标  
    int child = parent*2+1;  
    
    //每一轮交换进行的条件  
    while(child < end){  
        //右节点比左节点大的时候，但前提是右节点必须存在  
        if(child+1 < end && elem[child+1] > elem[child]){  
            child++;  
        }        
    	//调整过后，child代表的就永远都是更大的子节点  
        
        //当子节点比根节点大时，进行交换  
        if(elem[child] > elem[parent]){  
            swap(parent,child);  
            parent = child;  
            child = 2*parent+1;  
        }else {  
            //若子节点小于根节点，则跳出循环  
            break;  
        }    
    }
}

观察调试结果，可发现已变成大根堆

小根堆的实现

小根堆的实现只需要在大根堆实现的基础上将

child 的指向改为指向更小的那个节点： if (child + 1 < end && elem[child + 1] < elem[child]) {child++;}
parent 和 child 交换的条件改为 if (elem[child] < elem[parent])

小根堆的代码与大根堆相似度高达 99%，只需要将 shiftDown 方法中的第 7 和 13 行进行微微调整即可

public void shiftDown2(int parent, int end) {  
    //parent的值是作为参数传进来的，我们需要用parent的下标算出child的下标  
    int child = parent * 2 + 1;  
    //一轮交换进行的条件  
    while (child < end) {  
        //右节点比左节点大的时候，但前提是右节点必须存在  
        if (child + 1 < end && elem[child + 1] < elem[child]) {  
            child++;  
        }        
        //调整过后，child代表的就永远都是更小的子节点  
        
        //当子节点比根节点小时，进行交换  
        if (elem[child] < elem[parent]) {  
            swap(parent, child);  
            parent = child;  
            child = 2 * parent + 1;  
        } else {  
            //若子节点大于根节点，则跳出循环  
            break;  
        }   
    }
}

观察调试结果，可发现已变成小根堆