首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >二叉堆

二叉堆

作者头像
shysh95
发布2020-05-08 14:32:29
2120
发布2020-05-08 14:32:29
举报
文章被收录于专栏:shysh95shysh95

在我们用代码实现二叉堆之前,我们先了解一下几个技巧,二叉堆由于采用数组进行存储,所以我们定位一个节点只需要确认该节点在数组中的下表即可。

假设我们一个节点的数组下标为N,那么:

  • 左孩子节点:2N + 1
  • 右孩子节点:2N + 2

public class BinaryHeap {

 
 /**
 
     * 上浮
 
     * @param array
 
     */
 
 public static void upAdjust(int[] array) {
 
 int childIndex = array.length - 1;
 
 int parentIndex = (childIndex - 1) / 2;
 
 int temp = array[childIndex];
 
 while (childIndex > 0 && temp < array[parentIndex]) {
 
            array[childIndex] = array[parentIndex];
 
            childIndex = parentIndex;
 
            parentIndex = (childIndex - 1) /2;
 
 }
 
        array[childIndex] = temp;
 
 }
 


 
 /**
 
     * 下沉
 
     * @param array
 
     * @param parentIndex
 
     * @param length
 
     */
 
 public static void downAdjust(int[] array, int parentIndex, int length) {
 
 int temp = array[parentIndex];
 
 int childIndex = 2 * parentIndex + 1;
 
 while (childIndex < length) {
 
 if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
 
                childIndex++;
 
 }
 
 if (temp < array[childIndex]) {
 
 break;
 
 }
 
            array[parentIndex] = array[childIndex];
 
            parentIndex = childIndex;
 
            childIndex = 2 * parentIndex + 1;
 
 }
 
        array[parentIndex] = temp;
 
 }
 


 
 /**
 
     * 构建二叉堆
 
     * @param array
 
     */
 
 public static void buildHead(int[] array) {
 
 for (int i = (array.length - 2) / 2; i >= 0; i--) {
 
            downAdjust(array, i, array.length);
 
 }
 
 }
 


 
 public static void main(String[] args) {
 
 int[] array = new int[] {
 
 1, 3, 2, 6, 5, 7, 8, 9, 10, 0
 
 };
 
        upAdjust(array);
 
 System.out.println(Arrays.toString(array));
 


 
        array = new int[] {
 
 7, 1, 3, 10, 5, 2, 8, 9, 6
 
 };
 
        buildHead(array);
 
 System.out.println(Arrays.toString(array));
 
 }
 
}
 
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-05-05,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员修炼笔记 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档