TikTok OA Interview Question: 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

This question tests heap operation fundamentals: insertion should append the new element to the end of the array and restore the heap property with siftUp, while removing the top element should swap the root with the last element, delete the last element, and restore order with siftDown. The correct snippets are the ones that pair insert with siftUp and removeTop with siftDown.