Comparison Mode
Side-by-side: use case, requirements, complexity, strengths, weaknesses, example problems, and a clear “choose this when…”.
BFS vs DFSDijkstra vs Bellman-FordKruskal vs PrimMerge Sort vs Quick SortHeap vs Priority QueueHash Map vs Tree MapBFS vs DijkstraSliding Window vs Two PointersPrefix Sum vs Segment TreeGreedy vs Dynamic ProgrammingMemoization vs TabulationTarjan vs KosarajuSegment Tree vs Fenwick TreeArray vs Linked ListStack vs QueueQuick Sort vs Heap SortKMP vs Rabin-KarpUnion-Find vs DFSTrie vs Hash MapAVL Tree vs Red-Black Tree
HeapHeaps | Priority QueueStack/Queue | |
|---|---|---|
| Use case | The concrete array-backed tree that keeps the min (or max) at the root. | The abstract interface: insert with a priority, extract the highest priority. |
| Requirements | An array with parent/child index arithmetic ((i-1)/2, 2i+1, 2i+2). | Any backing structure: binary heap (usual), Fibonacci heap, balanced BST, sorted list. |
| Time complexity | Push/pop O(log n); peek O(1); heapify an array O(n). | Depends on the implementation; O(log n) insert/extract with a binary heap. |
| Space complexity | O(n), contiguous. | O(n). |
| Strengths | Cache-friendly; in-place heap sort; heapify is linear. | Lets you choose the implementation for the workload (e.g. decrease-key with a Fibonacci heap). |
| Weaknesses | No efficient search or arbitrary delete without an index map; no decrease-key by default. | Language built-ins often lack decrease-key or custom comparators; behaviour hidden behind the API. |
| Example problems | Kth largest element, heap sort, k-way merge implemented by hand. | Dijkstra, task scheduler, merge k sorted lists via the standard library. |
| Choose this when | Choose to reason about the heap when you need the array layout: heap sort, O(n) heapify, or an indexed heap with decrease-key. | Choose the priority-queue abstraction whenever you just need "give me the smallest next"; use the standard library implementation. |