Given the node at index i, its left child node can be found at index 2i + 1 and its right child node can be found at index 2i + 2. We have a little formula for calculating the child indices of any node. Notice how each level of the tree has twice as many nodes as the level above it. If we then used those indices to make an array, with each element stored in its indexed position, it would look like this:Ī bit of clever math now connects each node to its children. We start by assigning 0 to the root node, and then we iterate down through the levels, counting each node from left to right: Under the hood, the heap data structure is actually an array!Įvery node in the heap is assigned an index. If you’ve worked through the Binary Search Tree tutorial, it might surprise you to learn the heap data structure doesn’t have a Node data type to contain its element and links to its children. We keep sifting up until the new element has a lower priority than its parent, or it becomes the root of the heap.Īnd once again, the ordering of the heap is preserved. Then we compare the priority of the new element to its parent, and if it has a higher priority, we sift up. First we add the new element at the left-most position in the incomplete level of the heap: Adding a new elementĪdding a new element uses a very similar technique. Since every node once again has a higher priority than its children, the heap quality of the tree is restored. We keep sifting down until either the former last element has a higher priority than its children, or it becomes a leaf node. We compare the new child node with its children again, and swap it with the child with the highest priority. Now the new root node is the node with the highest priority in the tree, but the heap might not be ordered yet. Then, we compare the new root node to each of its children, and swap it with whichever child has the highest priority. Instead, we swap the root node with the last node in the heap. However, simply removing the root node would not leave behind a heap. The heap is useful as a priority queue because the root node of the tree contains the element with the highest priority in the heap. Whenever we remove nodes from a heap, we remove the rightmost node from the lowest level. Whenever we add nodes to a heap, we add them in the leftmost possible position in the incomplete level. Before a new level can be added, all the existing levels must be full. …then the heap has the fewest possible number of levels to contain all its nodes. If you think of the heap as having levels, like this:
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |