\nobjects in memory, the space from which you allocate the memory to
\ncreate them is called the heap. That is not<\/em> what I’m talking about.<\/p>\n
What I am talking about is an extremely simple but powerful structure
\nthat is used for maintaining a collection of values from which you want
\nto be able to quickly remove the largest object quickly. This may sound
\ntrivial, but this turns out to be an incredibly useful structure. You can use this basic structure to implement a very fast sorting algorithm; to maintain a prioritized set of values\/tasks; to manage chunks of memory; etc. (The
\nprioritized set is the most common case in my experience, but that’s probably because I’ve spent so much of my career working on distributed systems.)<\/p>\n
<\/p>\n
When you’re talking about data structures, one of the important things
\nyou need to do in order to really understand how to choose the best one is to understand exactly what properties a data structure provides: what operations need to be fast; what operations you need to have, but don’t care about the speed; how fast things need to be; how much memory you need to create
\none, and so on.<\/p>\n
In a heap, what we want is to be able to add an element Now, I haven’t yet defined what I mean by “quickly” in the above definition. There’s a good reason for that: there are a set of tradeoffs A binary heap is basically a binary tree with three properties, called So, for example, this figure is a binary heap. It’s got three levels. The first two levels are full; the third level is full on its left side. The next We can write a heap in a textual form using parens: we write each node To make it easier to read, we can stretch it across a couple of lines:<\/p>\n For the moment, we’ll ignore just how this tree is represented. We’ll get It should be obvious how to find the largest element – it’s the root of The way that we do this is called bubble-down<\/em> What we do is take the last element in the heap – the rightmost leaf – and insert it as the root. Now there’s no hole, but the heap isn’t valid. So we look at the two children of the root, and take the larger<\/em> one, and swap it with the root. Now the root is larger that both of its children, but the child-heap that now has a new root may be invalid. So we check it, and if it’s not valid, we repeat Let’s look at that with an example. Take the heap from the Now, we look at the two children, 10 and 7. 10 is larger, so we swap Now, we look at the modified subheap – the left child heap. Its two Now we’ve modified the left-left child subheap, and it’s invalid, so we Now our heap is valid again.<\/p>\n So how long did that take? We removed the root, and replaced it with What about adding an element? It’s basically the inverse of removing the root; it’s a bubble-up<\/em>. We insert the value into the position Let’s look at a quick example of insert. Say we wanted to insert 12 It’s larger than its parent, 5, so we swap:<\/p>\n And so on – we’ll swap two more times, giving us a new heap:<\/p>\n So again, we’re looking at a maximum of lg(n) swaps to I’m running out of writing time, so I’ll have to leave a One of the most neglected data structures in the CS repertoire is the heap. Unfortunately, the jargon is overloaded, so “heap” can mean two different things – but there is a connection, which I’ll explain in a little while. In many programming languages, when you can dynamically create objects in memory, the space from which […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[83],"tags":[],"class_list":["post-633","post","type-post","status-publish","format-standard","hentry","category-data-structures"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-ad","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/633","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=633"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/633\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=633"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nto the heap quickly, and to be able to remove the largest element quickly. We’re not<\/em> going to remove arbitrary elements of the heap: we only remove the largest. We can’t query the heap – that is, we can’t ask “Is X in the heap?” – all we can do is remove the largest value. And while providing these properties, we want to use as little memory as possible.<\/p>\n
\nthat produce different solutions. For now, we’ll settle for one
\nversion of “quickly”: O(lg n) – that is, in the worst case, the amount of time it takes to either remove the largest value, or to add a new value, is
\nproportional to the logarithm of the number of values in the heap. We can
\nprovide that kind of performance with a kind of heap called a binary heap<\/em>.<\/p>\n
\nthe heap properties<\/em> of the tree:<\/p>\n\n
\nits children.<\/li>\n
\nto the last leaf. (In other words, the last level is filled
\nleft to right.)\n<\/li>\n<\/ol>\n![\"heap-example.png\"](\"https:\/\/i0.wp.com\/scientopia.org\/img-archive\/goodmath\/img_305.png?resize=289%2C218\")
<\/p>\n
\ninsert point would be the next leftmost slot, the left child of 6.<\/p>\n
\nas a triple: (x, y, z), where x is the value of the parent, and y and z are the parenthesized heaps that are the children of x. So the same heap that I showed above can be written in text form as:
\n(11,(10,(9,(8,,),(2,,)),(5,(3,,),(1,,))),(7,(6,,),(4,,))).<\/p>\n\n(11,\n(10,\n(9,\n(8,,),\n(2,,)),\n(5,\n(3,,),\n(1,,))),\n(7,\n(6,,),\n(4,,)))\n<\/pre>\n
\nto that later.<\/p>\n
\nthe binary heap. But once we remove it, then we don’t have a heap: there’s a hole at the top – so part of the operation of removing the maximum element
\nhas to be re-validating the heap properties.<\/p>\n
\nthe bubble-down operation on that child-heap.<\/p>\n
\nfigure above. If we remove the largest element (11), and then
\nreplace it with the last element of the heap, we get the following
\ninvalid heap:<\/p>\n\n(1,\n(10,\n(9,\n(8,,),\n(2,,)),\n(5,\n(3,,),))\n(7,\n(6,,),\n(4,,)))\n<\/pre>\n
\nthe 1 and the 10, which gives us:<\/p>\n\n(10,\n(1,\n(9,\n(8,,),\n(2,,)),\n(5,\n(3,,),))\n(7,\n(6,,),\n(4,,)))\n<\/pre>\n
\nchildren are 9 and 5, both larger that 1. 9 is larger, so we swap:<\/p>\n\n(10,\n(9,\n(1,\n(8,,),\n(2,,)),\n(5,\n(3,,),))\n(7,\n(6,,),\n(4,,)))\n<\/pre>\n
\nagain swap for the larger child:<\/p>\n\n(10,\n(9,\n(8,\n(1,,),\n(2,,)),\n(5,\n(3,,),))\n(7,\n(6,,),\n(4,,)))\n<\/pre>\n
\nthe last child. That’s a couple of steps – not the dominant cost of the operation. Then\twe did the bubbledown – that’s the main cost. So how many
\nsteps are there in a bubbledown? In the worst case – like the example case above – you’ll need to do a number of swaps equal to the depth of the tree. The depth of the tree is lg(n), where n is the number of values in the tree. So we do at most lg(n) swaps – so the cost of removing the largest element
\nis O(lg n). <\/p>\n
\nafter<\/em> the last leaf. Then we compare the leaf to its parent. If it’s
\nlarger than its parent, we swap the node with its parent. And we repeat going
\nup the tree. <\/p>\n
\nto our heap. We’d start by adding 12 as a leaf:<\/p>\n\n(10,\n(9,\n(8,\n(1,,),\n(2,,)),\n(5,\n(3,,),\n(12<\/b>,,))\n(7,\n(6,,),\n(4,,)))\n<\/pre>\n
\n(10,\n(9,\n(8,\n(1,,),\n(2,,)),\n(12<\/b>,\n(3,,),\n(5,,))\n(7,\n(6,,),\n(4,,)))\n<\/pre>\n
\n(12,\n(10,\n(8,\n(1,,),\n(2,,)),\n(9,\n(3,,),\n(5,,))\n(7,\n(6,,),\n(4,,)))\n<\/pre>\n
\ndo an insert. So we’re O(lg n) for insert.<\/p>\n
\ndescription of how to represent a heap, and an example
\nimplementation of a heap for this evening. But I’ll leave you with one
\nquick example of how a heap can be used. Suppose I want to sort
\na list of integers. We know that the best worst-case time for
\nsorting is O(n lg n). We can implement a very simple sort by inserting all
\nof the values into a heap, and then removing them in order. That’s n inserts, each with maximum cost lg(n); and n removes, maximum cost lg(n). So it’s
\nO(n lg n) to sort the list – and no O(n2<\/sup>) case like quicksort!<\/p>\n","protected":false},"excerpt":{"rendered":"