Heaps, Stacks, Queues

Interview Essentials

• Heap: A tree-based data structure in which the value of a parent node is ordered in a certain way with respect to the value of its child node(s). A heap can be either a min heap (the value of a parent node is less than or equal to the value of its children) or a max heap (the value of a parent node is greater than or equal to the value of its children).

• Stack: Operations are performed LIFO (last in, first out), which means that the last element added will be the first one removed. A stack can be implemented using an array or a linked list. If the stack runs out of memory, it’s called a stack overflow.

• Queue: Operations are performed FIFO (first in, first out), which means that the first element added will be the first one removed. A queue can be implemented using an array.

Along with being comfortable with implementing heaps, stacks, and queues, it’s important to be clear on the the differences between these data structures. In interviews, it’s common to get questions like, “Explain the differences between a heap and a stack.”Heaps

What are Heaps?

The purpose of a min-heap is to store objects that have a partial order on them. It has a fast (O(log n)) method for removing the minimum object from the heap. Min-heaps are useful for calculations where you have multiple minimum computations to perform.

There is an analogous structure called a max-heap, which extracts the maximum value from the heap.

A heap is either a max-heap or a min-heap - it can't be both. Given an implementation of a min-heap, a max-heap can be implemented by reversing the comparison between elements. We're only going to discuss min-heap in the rest of this overview.

Heaps are sometimes referred to as priority queues. Technically, heaps are actually just one implementation of a priority queue.

Crucial Terms

• key: The values that determine the order. If you're storing numbers, the numbers can be the keys. If you're storing more complicated objects, the key is the data field that we're comparing by. Unlike in hash tables, keys in heaps do not have to be unique.

• extract_min: The method of (quickly) being able to extract the minimum element from the min-heap.

There are some implementation-specific details about heaps (such as the heap property and complete binary trees) that are useful for understanding how to build a heap from scratch, but they aren't that useful for using heaps to solve interview problems.

Strengths and Weaknesses

Strengths

• A min-heap is able to quickly extract the minimum value on the heap. Repeated extractions from a min-heap into an array will yield a sorted array.

Weaknesses

• There's no convenient way of searching for a particular key value in a heap. Entries are only partially ordered; clever use of the heap property can allow for some pruning of searches.

In Interviews, Use Heaps When ...

Heaps are designed to do one specific thing well, so the answer to when you should use a heap is repetitive: You use one when you have to do repeated minimum (or maximum) extractions. The problems where you would want to do this might look quite different from each other, however. Below we have selected some examples of common interview questions that benefit from heaps.

• Finding the minimum distance between two nodes in a graph: The standard approach to this problem is to use Dijkstra's algorithm. One of the key steps in Dijkstra's algorithm is to select the node closest to a node that you have already completed, which is a minimum calculation.

• Getting the next event that is scheduled to occur: Storing events in a heap with a timestamp as the key gives you a fast way to extract the next event (the event with the smallest timestamp will occur next).

• Keep track of the median value while streaming: This is the running median problem, where two heaps are maintained: a max-heap for values below the current median and a min-heap for values above the current median. When a new value is inserted, it is placed in the low or high pile as appropriate (and the maximum of the low values or minimum of the low values are extracted as necessary to keep the two heaps sizes' different by at most one element).

• Find the first k non-repeating characters in a string in a single traversal.

Common Operations Cheat Sheet

The operations described below are for a min-heap implemented using a full binary tree. There are obvious analogs for a max-heap.

Operation	Description	Time complexity	Mutates structure
insert(key)	Inserts key into heap. Can modify to have a key/value pair.	O(log n)	Yes
extract_min()	Returns and removes item with minimum key from the heap,	O(log n)	Yes
peek_min()	Can view minimum key, doesn't remove it from the heap	O(1)	No
heapify(list)	Creates a new heap from a list of n items. Functionally equivalent to starting with an empty heap and inserting elements one at a time, but has a better run time than the O(n log n) of this approach.	O(n)	N/A (creates heap)

There are other ways of constructing heaps (such as binomial heaps and Fibonacci heaps) that can improve the asymptotic run time slightly, but that support the same operations.

Stacks and Queues

What Are Stacks and Queues?

Stacks and queues are grouped together because they share many of the same properties. They are both data structures designed to hold elements and return them in a specific order. The difference between the data structures is the order in which items are retrieved.

• Stacks are First In, Last Out / Last In, First Out: Consider a literal stack of books. When you put a book on the top of the stack, you have to remove it before you can access the books underneath. The book at the very bottom isn't accessible until you have removed all the other books on top of it.

  

  If elements are added to a stack in the order [A,B,C,D,E], they will be removed in the order [E,D,C,B,A], assuming all the arrivals happened before the removals started.

• Queues are First In, First Out: In a line (or queue) at a bank, the first person to arrive is the first person to be served. When using a queue to store data, the first elements in are the first elements out.

  

  If elements are added to a queue in the order [A,B,C,D,E], they will be removed in the same order ([A,B,C,D,E]), even if the arrivals and removals are interweaved.

  (The animation suggests that the elements in queue "move forward" when the first one is removed. In efficient implementations of queues, the elements that are not leaving the queue stay in place, so dequeuing can be implemented as an O(1) operation.)

Because of the metaphors used, we often talk about the "top" and "bottom" of a stack, but the "front" and "back" of a queue.

Stacks and queues are both abstract data types, which means that we are guaranteed to be able to put elements in and remove them in the specified order. You can build a stack or queue out of whatever data structures you like, such as arrays or linked lists, if you provide a way to add elements in the correct order. For example, in Python, the standard list acts like both an array and a stack.

Crucial Terms

Stacks and queues both have an add operation (push/enqueue) and a remove operation (pop/dequeue).

• push: (stack) The generic term for adding an object to the "top" of the stack.

• pop: (stack) The generic term for removing the object from the "top" of the stack.

• enqueue: (queue) The generic term for adding an object to the "back" of the queue.

• dequeue: (queue) The generic term for removing an object from the "front" of the queue.

The name of the functions can differ from those shown above, depending on how you're implementing the stack or queue and the programming language you use. When using a Python list as a stack, for example, using L.append(item)is the push command, but Python does support a L.pop() command.

A slick implementation of an object that is both a stack and a queue is to use a doubly linked list, with a reference to the head and tail elements. This doubly linked list could implement all four functions above with O(1) time complexity.

Common Operations Cheat Sheet

Because stacks and queues are abstract data types, there is some debate whether time complexity is appropriate for the methods. The debate stems from questions of whether adding and removing from stacks and queues are the only thing they have to do (and time complexity is an implementation detail), or whether the time complexity is intrinsic to the definition of stacks and queues. For the table below, we have chosen the pragmatic option of including the time complexity as part of the definition, since your choice to use a stack or a queue over some other data structure is presumably because they support quick addition and removal of data in the order you want to access it.

If you are using a multipurpose data structure like Python's list (which is a stack and a queue), rather than an optimized queue or stack, you will probably have worse performance than indicated below.

Stack Operation	Description	Time complexity	Mutates structure
push(item)	Pushes item on the "top" of the stack	O(1)	Yes
pop()	Removes the most recently added item from the stack. (i.e. the item on "top")	O(1)	Yes
peek()	Accesses the most recently added item in the stack, without removing it	O(1)	No
isEmpty()	Returns True if there are no items on the stack, Falseotherwise	O(1)	No

Queue Operation	Description	Time complexity	Mutates structure
enque(item)	Puts item at the end of the queue	O(1)	Yes
deque()	Removes the item at the front of the queue	O(1)	Yes
peek()	Accesses the item at the front of the queue, without removing it	O(1)	No
isEmpty()	Returns True if there are no items in the queue, Falseotherwise	O(1)	No