Binary heaps

A binary heap is a binary tree with two constraints: the heap order property and the structure property. The heap order property ensures that child nodes are always ordered with respect to their parent. The structure property ensures we have a complete binary tree. With these two properties, we get some pretty interesting and useful behaviors, in addition to a very efficient representation as a vector!

Binary heap data structure is widely used in priority queues.

Here鈥檚 a brief introduction to binary heaps (13:08).

Additional reading

Resources

• Binary_Heap.pdf

Comprehension check:

1. A binary heap is a _________________________ binary tree with the heap order property.
2. The heap property imposes a(n) ____________________ on the nodes with respect to their values.
3. To insert a node, we may need percolate ____________ to find the correct position for the inserted value.
4. True or false? Every complete tree is perfect.
5. In an array representation of a heap, if a node is at index i, its children (if they exist) will be at indices ____________ and _____________.
6. The complexity of insert and delete minimum operations is __________________.

Answers: (N 苾ol)O / 茤+u釀� pu蓯 u釀� / 菨sl蓯蔁 / dn / 苾u岽壣骨漰晒o / 菨蕠菨ld莎o蓴

Copyright 漏 2023鈥�2025 Clayton Cafiero

No generative AI was used in producing this material. This was written the old-fashioned way.