时间戳

首页 > 解决方案 > 这是minheap的排序方式吗？

java - 这是minheap的排序方式吗？

问题描述

我的教授声称我的 Minheap 在以下问题上不正确：

使用min heap down将以下数字转换为minheap并逐级绘制最终的 minheap 树和最终的数组内容。

给定数组：100 10 80 30 60 50 40 70 20 90

我的回答如下：

                     10
                /          \
             20             40
            /  \           /  \
          30    60       80    50
          /\    /
        100 70  90

排序数组：10,20,40,30,60,80,50,100,70,90

我不正确吗？

标签： java

解决方案

Min-Heap 是一棵完全二叉树，其中每个内部节点中的值都小于或等于该节点子节点中的值。将堆的元素映射到数组中很简单：如果一个节点存储了一个索引 k，那么它的左子节点存储在索引 2k + 1 处，而它的右子节点存储在索引 2k + 2 处。

你的答案是对的，你错过了 70 和 100，这是错误的，否则它是正确的

排序后的数组将是

10,20,40,30,60,50,80,70,100,90

推荐阅读