Interval problems look like a family of tricks. They are one trick applied seven ways, and the trick fits in a sentence: sort by start time, and every question about overlap becomes a question about the element you just looked at. Without the sort, “do any two of these overlap?” is a pairwise check over n² pairs. With it, an interval can only overlap the ones immediately around it, so one linear walk answers the question. Three of the seven problems below need nothing more than that walk. The other four need one extra structure — a heap — and READ MORE
Tag: Priority Queue
LeetCode Queue Design Patterns in C++: Put the Answer at an Edge
LeetCode Queue Design Patterns in C++: Put the Answer at an Edge LeetCode Queue Design Patterns in C++: Put the Answer at an Edge nycomdorics.com · preview of the WordPress post · source deck by Joseph Choi A binary heap will hand you its smallest element instantly and tell you nothing whatsoever about the second smallest. A std::vector will append and remove at the back in constant time and charge you a full shift to remove from the front. Every structure in this family is generous at its edges and useless in its interior. So the design job is always READ MORE
Priority Queues & Binary Heaps Explained: How They Work Under the Hood
Imagine a hospital emergency room. Patients don’t get seen in the order they arrived — they get seen based on the severity of their condition. A patient with a heart attack jumps ahead of someone with a sprained ankle, regardless of who checked in first. That’s exactly the problem a priority queue solves in software. In this post, we’ll cover what priority queues are, how the binary heap makes them efficient, and how the core operations — insertion, extraction, and heapify — actually work. What Is a Priority Queue? A priority queue is a specialized version of a regular queue. READ MORE