heaps.md

Heaps

Table of contents

• General information
• Binary heaps

---

General information

A heap is a tree-based data structure which is an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key of P is greater than or equal to the key of C.

🔗

• Heap – Wikipedia

Binary heaps

🔗

• Binary heap – Wikipedia

❔

• Argument for O(1) average-case complexity of heap insertion – Stack Overflow
• Amortized analysis on min-heap? – Stack Overflow
• How to implement O(log n) decrease-key operation for min-heap-based priority queue? – Stack Overflow

📖

• Ch. 10: The heap data structure – Roughgarden T. Algorithms illuminated (Part 2): Graph algorithms and data structures – Soundlikeyourself Publishing (2018)