Heaps — Simple English

31 lessons · Data Structures & Algorithms · Simple English · Beginner Friendly

01 Why We Need a Priority Data Structure (The Problem Behind Heaps)Free Why We Need a Priority Data Structure Before learning what a heap is, it helps to first feel the problem that a heap was… 02 The Priority Queue: Always Serving the Most Important FirstFree The Priority Queue: Always Serving the Most Important First Earlier we tried to keep track of priorities using a linked … 03 Understanding a HeapFree Understanding a Heap A little while ago we met the idea of a priority queue — a line where the most important item alway… 04 Types of Heaps: Max Heap and Min Heap🔒 Types of Heaps: Max Heap and Min Heap A heap is a special tree where every node carries a value, and the values are arra… 05 Heap Operations: Insert, Delete, Peek, Extract, and Construct🔒 What You Can Do With a Heap You already know that a heap is a special tree that always keeps the most important item at … 06 Checking if a Binary Tree is a Valid Min Heap🔒 Checking if a Binary Tree is a Valid Min Heap Imagine you have a family tree of numbers. Each number sits in a circle, a… 07 How a Heap is Stored in an Array🔒 How a Heap is Stored in an Array A heap is a special kind of complete binary tree. "Complete" means the tree fills up le… 08 Inserting a New Value into a Max-Heap (Up-Heapify)🔒 Inserting a New Value into a Max-Heap A heap is a special kind of binary tree that we usually store inside a plain array… 09 Deleting an Item from a Max-Heap (Down-Heapify)🔒 Deleting an Item from a Max-Heap Deleting is one of the main operations you can do on a heap. The idea is simple to say … 10 Peeking the Top Item in a Max Heap🔒 Peeking the Top Item in a Max Heap A max heap is a special kind of tree where every parent is bigger than (or equal to) … 11 Extracting the Maximum Value from a Max Heap🔒 Extracting the Top Item from a Max Heap A max heap is a special tree stored inside an array, where the biggest value alw… 12 Constructing a Max Heap from an Array🔒 Constructing a Max Heap from an Array So far you may have learned how to add items into a heap one at a time. But what i… 13 Turning a Min Heap Into a Max Heap In Place🔒 Turning a Min Heap Into a Max Heap In Place A heap is a special way of arranging numbers in an array so that they behave… 14 Converting a Max Heap into a Min Heap🔒 Converting a Max Heap into a Min Heap First, a quick refresher on heaps A heap is a special kind of binary tree that we … 15 The Top K Elements Pattern: Finding the Best K Items with a Heap🔒 The Top K Elements Pattern Imagine you have a long list of numbers and someone asks you: "Give me the 4 biggest ones, an… 16 The Top K Elements Pattern: Finding the K Largest Items with a Min-Heap🔒 The Top K Elements Pattern Imagine you have a big list of numbers, and you only care about the biggest few of them — say… 17 Finding the Kth Largest Element Using a Heap🔒 Finding the Kth Largest Element Imagine you have a list of numbers and someone asks you: "What is the 2nd biggest number… 18 Finding the Kth Smallest Element Using a Heap🔒 Finding the Kth Smallest Element Imagine you have a bag of numbers and someone asks you: "What is the 2nd smallest numbe… 19 K Range Sum: Adding Up Values Between Two Ranked Elements🔒 K Range Sum This is a small puzzle that mixes two ideas you already know: sorting numbers by size, and adding up a group… 20 Sorting a Nearly Sorted (K-Sorted) Array with a Min-Heap🔒 Sorting a Nearly Sorted (K-Sorted) Array Sometimes an array is almost sorted, but not quite. Every number is close to wh… 21 Comparators: Teaching a Heap How to Order Your Own Data Types🔒 Comparators: Teaching a Heap How to Order Your Own Data Types First, a quick reminder about heaps A heap is a special ki… 22 The Comparator Pattern: Using a Heap with a Custom Comparator🔒 The Comparator Pattern: Sorting Your Own Data Types in a Heap A heap is a special container that always keeps track of i… 23 The Comparator Pattern: Finding the Top K Items with a Heap🔒 The Comparator Pattern: Finding the Top K Items Some problems share a hidden shape. Once you learn to spot that shape, y… 24 Finding the K Most Frequent Elements Using a Heap🔒 K Most Frequent Elements Imagine you have a big list of numbers, and some numbers show up many times while others appear… 25 Finding the K Pairs With the Smallest Sums🔒 Finding the K Pairs With the Smallest Sums Imagine you have two lists of numbers. From the first list you pick one numbe… 26 Finding the K Closest Values in a Binary Search Tree🔒 Finding the K Closest Values in a Binary Search Tree Imagine you have a collection of numbers stored in a special kind o… 27 Smallest Range Covering K Sorted Arrays🔒 Smallest Range Covering K Sorted Arrays Imagine you have several lists of numbers. Each list is already sorted from smal… 28 Merging K Sorted Linked Lists Into One Sorted List🔒 Merging K Sorted Linked Lists Imagine you have several lines of people, and each line is already arranged from shortest … 29 Designing Your Own Max Heap Class🔒 Designing Your Own Max Heap A heap is a special way to store numbers so that the biggest (or smallest) one is always eas… 30 Designing a Min Heap: The Operations You Must Build🔒 Designing a Min Heap A heap is a special way to store numbers so that the smallest (or largest) one is always easy to fi… 31 Design a Median Finder for a Stream of Numbers🔒 Finding the Median of a Running Stream Imagine numbers arriving one at a time, like scores being read out during a game.…