Sift-down

释义 Definition

sift-down（也常写作 siftdown 或 sift down）：（计算机）在堆（heap）中把某个结点向下移动，通过与子结点比较并交换，使其重新满足堆性质的操作；常用于建堆或删除堆顶后的修复。也可称为 down-heap / heapify-down。

发音 Pronunciation (IPA)

/ˈsɪft daʊn/

例句 Examples

After removing the top element, the program performs a sift-down to restore the heap.
删除堆顶元素后，程序会执行一次 sift-down 来恢复堆的性质。

To maintain efficiency, the priority queue implementation uses sift-down operations during delete-min, ensuring the smallest key remains at the root.
为了保持高效率，这个优先队列在执行 delete-min 时使用 sift-down 操作，确保最小键值始终位于根结点。

词源 Etymology

sift 原意是“筛、筛选”（像用筛子把细的留下、粗的分开），引申为“通过比较与筛选来把不合适的部分移走”。在堆结构里，sift-down 形象地表示把“位置不合适”的结点一路向下“筛”到合适的位置，从而恢复有序性。

相关词 Related Words

• Heap
• Heapify
• Sift-up
• Priority
• Queue
• Swap
• Invariant

文学与著作 Notable Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein，常简称 CLRS）：在二叉堆/优先队列相关章节讨论与 heapify（含向下调整思想）相关的操作。
• Algorithms（Robert Sedgewick, Kevin Wayne）：在堆与堆排序内容中讲解类似 sift-down 的下沉/下滤操作。
• The Art of Computer Programming, Vol. 3: Sorting and Searching（Donald E. Knuth）：在堆与排序相关讨论中涉及与“下沉调整”同类的堆维护思想。