Which will do?

Computer Science Level 1

What data structure is required for storing a set of integers such that deletion of the smallest element and insertion of an element not already present in the set can each be done in $O(\log n)$ time?

A min-heap but not a balanced binary search tree Neither a min-heap nor a balanced binary search tree A balanced binary search tree but not a min-heap Both a min-heap and a balanced binary search tree

1 solution

Aksel V
Dec 11, 2018

Searching a binary tree of size N, requires only log N operations. While a heap is pretty much just that, a non-sorted bunch of numbers. Example: searching for the smallest number in a tree of 8 numbers, only require you to do 3 operations. First (1) you choose between which branch of 4 numbers each you want to go along. Then (2) you choose which branch with 2 numbers each you want to go along. For the third and last operation you choose which of the branches with 1 number each. When you are on a branch with only 1 number on it, you are done.

What kind of heap are you referring to as a "non-sorted bunch of numbers"? A heap, whether it be a binary heap or binomial heap or some other flavour, satisfies some heap property (typically min-heap or max-heap). So given a binary min-heap, deletion of the smallest element means deleting the root and making the smaller of its children the new root (and continuing down the sub-tree). This is logarithmic in the number of nodes. Insertion in a heap is also logarithmic in #nodes, since at most the full height is traversed. What am I missing?

Fredrik Mattisson - 2 years, 3 months ago

You're right, Beakal Tiliksew probably meant the deletion of a generic element.

Federico Biagi - 1 year, 11 months ago

Same as Fredrik Mattisson: imho a min-heap should also perform the mentioned operations in log(n) time.

J T - 1 year, 9 months ago

I second - Deleting and inserting a node in min/max heap costs O(log(n)). Answer by 'Brilliant' is incorrect and should instead be 'Both a heap and balanced Binary Search Tree". Anyone agree with me?

Yousif Atique - 1 year, 5 months ago

Which will do?

1 solution

0 pending reports