So we don't need explicit links at all to represent these data structures, we can just use array indices. And going the other way, it's easy to see that the children of the node at k are 2k and 2k plus 1. So both of those are 10 over 2, 11 over 2 integer divide is 5. So the parents of say H and G are both N, H is at 10 G is at 11, N is at 5. For example, if the node is at position k, index k in the array then its parent is at k over 2 and that's the integer divide. The other thing is as I just mentioned, you can use the array indices to move through the tree. It's larger than the keys in this two children and they're larger than theirs and so forth, so it's the largest key in the data structure. Well, the first thing is that a of 1 is the largest key. So that's complete binary trees represented in array with keys in the nodes, satisfying heap order property. So let's look at a few properties of binary heaps. The way that we move around the tree is by doing arithmetic on the indices. This is interesting because we can draw the tree to get more intuition about what's happening, but in the actual data structure representation, we don't need any links at all, it's just an array. So first we put the root, then we put the two nodes on the first level going left from right, and then all the nodes on the third level going from left to right and so forth. And then we just take the nodes in level order. The array representation, all we do is we put, we start with indices at 1. And the idea is that the parent's key is going to be no smaller than its children's key, and that's true for every node in the tree. So when we start putting the keys in the nodes, we're going to impose one more condition that's called heap ordering. And also we're going to represent it with an array. All right, now the way we're going to use a complete binary trees to implement priority queues is to first of all associate information with each node. Here's an example of one that goes one, two, three, four levels at least. Complete binary trees actually happen in nature. And that's really easy to convince yourself that that's true because the height if we add nodes one at a time going from left to right on the bottom level say, the height only increases when N is the power of 2. The property of a complete tree is at the height of a complete tree with N nodes is the biggest integer less than log base 2 of N. And we'll see how that looks in just a second. So there might be a few nodes on the bottom level and one level lower than the bottom level, but otherwise all the levels are full. A complete binary tree is one that's perfectly balanced, except possibly for the bottom level. Well, first of all, a binary tree is either empty or it's a node with links to left and right binary trees. So the idea of a binary heap is based on the idea of a complete binary tree. Now we're going to look at binary heaps, which is an ingenious and very simple data structure that's going to help us implement all the priority queue operations quickly.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |