TikTok OA 面试真题解析：Heap Operations Complexity｜堆插入与删除操作

1. Heap Operations Complexity

A heap is a special type of binary tree in which every parent node is less than or equal to its child node(s) (min-heap) or greater than or equal to its child node(s) (max-heap). This property must be recursively true for all subtrees in that binary tree.

Given the following Heap class:

Class Heap {
    array
    // methods
    insert(element) // inserts an element into the heap and maintains the heap property
    removeTop() // removes and returns the top element of the heap, and restores the heap property
    heapify() // transforms an arbitrary array into a heap}

The task is to correctly implement the insert(element) and removeTop() methods considering they should run in O(log n) and O(1) time complexities respectively.

• insert(element) method: adds a new element to the heap, maintaining the heap property, which requires the operation siftUp, where the added element is moved up the heap until the heap property is restored.
• removeTop() method: removes the top-most element, and to restore the heap property, it employs siftDown, moving down the heap accordingly.

Which of the following code snippets achieves this?

Pick ONE OR MORE options

这道题考察堆（heap）的基本操作实现逻辑：插入新元素时，应先把元素放到数组末尾，再通过 siftUp 向上调整，因此对应的实现是 <code>insert</code> 追加元素并上滤；删除堆顶时，应先将堆顶与末尾元素交换、删除末尾元素，再通过 siftDown 从根节点向下调整。题目本质上是在判断哪组伪代码正确匹配了堆的维护方式：插入用上滤，删除堆顶用下滤，而不是反过来。