Skip to content
dsa450for five year olds

Topic 10 of 15

Heap

A line where the smallest kid is always first.

A heap is a tree where every parent is smaller than its children, so the smallest thing is always at the top. It lives inside a plain array: the children of spot i are at 2i + 1 and 2i + 2. Use it whenever you keep asking "what is the smallest right now?"

What you will be able to do

Sift up and sift downTop k with a heap of size kMerging k sorted thingsTwo heaps for a running medianHeapsort
0/18
18 problems

Meet the heap

01 / 04

heap
136598012345136598

A min heap. Every parent is smaller than its children, so 1 is at the top. Below it is the same heap as an array.

  • looking now
  • checking
  • done
  • answer
  • just added

The problems

In order from easier to harder ideas. The ones marked must do come up in interviews again and again.

  1. 01Implement a Maxheap MinHeap using arrays and recursionBuild a pile of numbers where the biggest (or smallest) one always sits on top, stored inside a plain array.Heap basics
  2. 02Sort an Array using heap (HeapSort)Sort numbers by making the biggest one float to the top again and again, and parking it at the back of the line.Heap sort
  3. 03Maximum of all subarrays of size kSlide a window of k boxes along a row and say the biggest number in the window at every stop.Monotonic deque
  4. 04k largest element in an arrayKeep only the k biggest numbers you have seen in a small club where the weakest member sits by the door.Heap of size k
  5. 05Kth smallest and largest element in an unsorted arrayFind the number that would stand k-th from the short end, and k-th from the tall end, without lining everyone up.Heap of size k
  6. 06Merge K sorted arraysSeveral sorted lines of numbers become one sorted line by always taking the smallest front number, found fast with a min heap.K way merge with a heapMust do
  7. 07Merge 2 Binary Max HeapsPour two pyramids of numbers into one row and fix the new pyramid from the bottom up.Build heap
  8. 08Kth largest sum continuous subarraysLook at the total of every unbroken stretch of numbers and find the k-th biggest total, keeping only k totals at a time.Heap of size k
  9. 09Leetcode reorganize stringsRearrange letters so no two equal letters touch, always placing the letters that are most left over first.Greedy with a max heap
  10. 10Merge K Sorted Linked ListsZip several sorted chains of boxes into one sorted chain by always unhooking the smallest front box, found with a min heap.K way merge with a heapMust do
  11. 11Smallest range in K ListsFind the shortest stretch of the number line that catches at least one number from every sorted list.K way merge with a heap
  12. 12Median in a stream of IntegersNumbers arrive one at a time and after each one you must say the middle number, using two piles that meet in the middle.Two heaps
  13. 13Check if a Binary Tree is HeapCheck that a tree has no holes when filled row by row, and that every parent is at least as big as its children.Tree walk with array indexes
  14. 14Connect n ropes with minimum costTie many ropes into one, paying the length of every new rope you make, and always tie the two shortest first.Greedy with a min heap
  15. 15Convert BST to Min HeapPour the sorted numbers of a search tree back into the same tree in a new visiting order, so the tree becomes a min heap.Inorder then preorder fill
  16. 16Convert min heap to max heapTurn a pyramid with the smallest number on top into one with the biggest on top, fixing it from the bottom up.Build heap
  17. 17Rearrange characters in a string such that no two adjacent are sameLine up letters so no two equal ones stand together, by always using the most common letter that did not just go.Greedy with a max heap
  18. 18Minimum sum of two numbers formed from digits of an arrayDeal digit cards to two players, smallest first, so the two numbers they build add up to as little as possible.Greedy with a min heap
Next topicGreedy