Exams › GATE › Technical

Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation EXTRACT-MAX(A) extracts and deletes the maximum element from A. The operation INSERT(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations. When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?

1. Both EXTRACT-MAX(A) and INSERT(A,key) run in O(1).
2. Both EXTRACT-MAX(A) and INSERT(A,key) run in O(log(n)).
3. EXTRACT-MAX(A) runs in O(1) whereas INSERT(A,key) runs in O(n).
4. EXTRACT-MAX(A) runs in O(1) whereas INSERT(A,key) runs in O(log(n)).

Correct answer: Both EXTRACT-MAX(A) and INSERT(A,key) run in O(log(n)).

Solution

Both operations, EXTRACT-MAX and INSERT, involve maintaining the heap property, which requires traversing the height of the heap. Since a max-heap is a complete binary tree, the height is logarithmic in relation to the number of elements, leading to a worst-case time complexity of O(log(n)) for both operations.

Related GATE Technical questions

• Which one of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
• Let SLLdel be a function that deletes a node in a singly-linked list given a pointer to the node and a pointer to the head of the list. Similarly, let DLLdel be another function that deletes a node in a doubly-linked list given a pointer to the node and a pointer to the head of the list. Let n denote the number of nodes in each of the linked lists. Which one of the following choices is TRUE about the worst-case time complexity of SLLdel and DLLdel?
• Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0,1}, and has the set of states {s,p,q,r}, with s being the start state and p being the only final state. Which one of the following regular expressions correctly describes the language accepted by A?
• Which one of the options given below refers to the degree (or arity) of a relation in relational database systems?
• Suppose two hosts are connected by a point-to-point link and they are configured to use Stop-and-Wait protocol for reliable data transfer. Identify in which one of the following scenarios, the utilization of the link is the lowest.
• An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let k be the number of keys, m be the number of slots in the hash table, and k > m. Which one of the following is the best hashing strategy to counteract the adversary?

⚔️ Practice GATE Technical free + battle 1v1 →