RoyNewDawn
RoyNewDawn
采纳率8.3%
2019-11-11 18:17 阅读 135

用向上调整建立一个二叉堆时候如何遍及其根结点?(C++实现)

在这里,我有一个疑惑,我这样建堆是无法遍及root的,假设根结点和其左孩子逆序,这里parent计算的结果是0,无法进入循环,所以根节点总是不能动的
循环结束的条件又无法改变,仅当parent=-1/2取整为0时结束循环,用dowhile也不行,假如根节点和左孩子不是逆序的你也做了一次交换是不行的。请教各位有什么解决办法吗?我附上了简单的测试代码

//大根堆
int percolateUp(int *arr, int rank) {
    int parent = (rank-1)/2;
        while (parent>0)
        {
            if (arr[rank] < arr[parent]) break;
            std::swap(arr[rank], arr[parent]);
            rank = parent;
            parent = (parent - 1) / 2;
        }
    return parent;
}
//一种低效的建堆方式
void heapify(int *arr, int n) {
    for (int i = 1; i < n; i++) {
        percolateUp(arr,i);
    }
}
int main() {
    int a[6]{ 1,2,3,4,5,6 };
    heapify(a, 6);
    for (int i = 0; i < 6; i++) {
        std::cout << a[i] << " ";
    }
}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享

1条回答 默认 最新

相关推荐