为什么堆排序中要使用sink来构建堆而不是swim?

问题描述 投票:0回答:1

《算法第4版》2.4。里面提到,在堆构建中,从右向左进行,使用sink()来创建子堆效率更高。但为什么???

我想知道为什么。为什么??????????我认为从左到右进行是一样的,使用 Swim()

algorithm sorting heap
1个回答
0
投票

在构造二叉堆时,出于多种原因,选择从右向左进行的“sink”操作会更有效。与从左侧“游泳”相比,从右侧开始使用“水槽”可以避免浪费工作。 “Sink”对于在部分有序堆构建阶段在较小的子堆内建立局部排序特别有效。这种方法最大限度地减少了不必要的移动,并从改进的缓存局部性中受益,使其成为优化堆构造的务实选择。虽然“swim”和“sink”之间的选择取决于具体的实现细节和数据特征,但本书的指南建议使用“sink”来实现高效的自下而上的堆构建过程。

© www.soinside.com 2019 - 2024. All rights reserved.