Issue 17 ~ 5/12/2017
"Heap," like "hash" is a term that can mean many things. Depending on the context, it could be a special kind of binary tree, the pool of memory that's available to be used by a C program, or the structure inside of MRI that holds every object that your Ruby program creates.
Each of these is different, but they're all interesting. With the single word "heap," we move all the way from basic computer science through low-level programming and into Ruby. Let's dive in!
Imagine your family tree, with you at the top. On the level below you are your two parents. Below them are their parents. Now imagine that instead of each person's name, you wrote their age. This is a binary heap.
- It's shaped like a tree
- Every node has two nodes below it (except on the last row)
- Every node is "younger" than the nodes below it.
Binary heaps are used in the famous-but-not-very-useful heapsort algorithm, and to implement priority queues.
Stacks and Heaps
In Ruby we tend to not worry about memory. We create objects, and don't worry too much about how those objects are stored in RAM.
Developers working in lower-level languages like C, C++, and Rust often need much better control over how memory is allocated. One of the most basic decisions that has to be made for each variable is: will it be stored on the stack or on the heap?
The Ruby heap is the data structure inside MRI that holds every object that your program creates. By doing a "heap dump," you can inspect these objects, which is a useful way to find problems like memory leaks and inefficient patterns of object allocation.
Like Walt Whitman, the word "heaps" contains multitudes. As a Rubyist, you may not need to ever do a heap dump. You probably won't ever need to implement a heapsort, except as a dumb interview question. And you definitely don't need to worry about manual memory allocation. But by understanding these disparate topics we gain a better understanding of how the systems we build work, and we give ourselves better options when designing new systems.