English
Menu

Data Structures and Algorithms

A max-heap, in which each parent's value is at least as large as its children's, is stored in an array with the root at a[0]. 45 is added to the heap 50, 30, 40, 10, 20, 35 by placing it at the end and then swapping it with its parent as long as it is larger than the parent. What is the resulting array?

  1. A50, 30, 40, 10, 20, 35, 45
  2. B45, 30, 50, 10, 20, 35, 40
  3. C50, 30, 45, 10, 20, 35, 40
Show answer and explanation

Answer: C. 50, 30, 45, 10, 20, 35, 40

45 is placed at a[6], whose parent is a[(6−1) ÷ 2] = a[2] = 40. Since 45 > 40, they are swapped and 45 moves to a[2]. Its next parent, a[0] = 50, is larger than 45, so the process stops, giving 50, 30, 45, 10, 20, 35, 40. Swaps happen at most as many times as the height of the tree, so insertion takes O(log n), and removing the maximum is also O(log n). For this reason, binary heaps are commonly used to implement priority queues.

  • A. It has only been placed at the end; it was not swapped even though it is larger than its parent 40.
  • B. This moves 45 all the way to the root, although it is smaller than the root 50.
  • C. Correct. After swapping with 40, it stops because its parent 50 is larger.
Practice this topic Back to topic

Related calculators

Binary search tree and heap visualizerDraw the binary search tree or heap built by inserting values in order, and show the preorder, inorder and postorder traversals, the search path and the heap's array layoutSorting algorithm visualizerWatch 7 sorting algorithms (bubble, selection, insertion, shell, merge, quick and heap) step by step as bar charts, and compare their comparison and write counts

Books on Data Structures and Algorithms Ad

As an Amazon Associate I earn from qualifying purchases.

More Data Structures and Algorithms questions

  1. When a binary search tree is traversed in in-order (visiting the left subtree, then the node, then the right subtree), how are the values of the visited nodes ordered? Assume all values are distinct.
  2. The values 50, 30, 70, 20, 40, 60, 80 are inserted in this order into an empty binary search tree. In what order are the nodes visited when the tree is traversed in post-order (left subtree, right subtree, then the node)?
  3. The values 1, 2, 3, …, 1000 are inserted in this order into an empty binary search tree (no rebalancing is done). When searching this tree for 1000, how many nodes are compared, starting from the root, before it is found?
  4. What is the main reason that B-trees (including B+ trees), rather than binary search trees, are widely used for indexes in databases and file systems?
  5. Which is an appropriate way to store in memory a sparse graph, one with few edges compared with its number of vertices, such as a road network with about 1 million vertices and 3 million edges?