What is Binary heap?

A complete binary tree in which each parent's value is greater than or equal to (max-heap) or less than or equal to (min-heap) its children's values. It can be stored in an array: with the root at a[0], the children of a[i] are a[2i+1] and a[2i+2]. Reading the maximum (minimum) takes O(1), and insertion and removal take O(log n); it is used for priority queues and heapsort.

Japanese name: 二分ヒープ

Binary heap appears in 2 practice questions across 1 topic, including Data Structures and Algorithms.

Field: Data Structures and Algorithms

Try it: questions about Binary heap

A binary heap is stored in an array a[0], a[1], a[2], … with the root at a[0], filling each level from left to right starting at the top. Which are the children and the parent of a[4]?

AChildren a[9] and a[10]; parent a[1]
BChildren a[8] and a[9]; parent a[2]
CChildren a[9] and a[10]; parent a[2]

Show answer and explanation

Answer: A. Children a[9] and a[10]; parent a[1]

With the root at a[0], the children of a[i] are a[2i+1] and a[2i+2], and its parent is a[(i−1) ÷ 2, rounded down]. For i = 4, the children are a[9] and a[10] and the parent is a[(4−1) ÷ 2] = a[1]. With the root at a[1], the children are a[2i] and a[2i+1] and the parent is a[i ÷ 2], so it is important to check which convention is being used. Because a heap is a complete binary tree, it can be stored in an array without pointers, and parents and children are found by index arithmetic alone.

Binary heap in the explanations

Heapsort builds a binary heap inside the array and repeatedly swaps the maximum at the root with the last element and shrinks the heap, so it runs in O(n log n) even in the worst case and needs only a constant amount of extra memory.
Which sorting algorithm is O(n log n) even in the worst cas…

Questions that mention Binary heap (2)

Books on Data Structures and Algorithms Ad

Search Amazon for semiconductor Data Structures and Algorithms

As an Amazon Associate I earn from qualifying purchases.

Semiconductor, Electronics and Computing Calculators

Sorting 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 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 layout

Back to the glossary