Lecture Note
University
University of California San DiegoCourse
CSE 100/101 | Data Structures and AlgorithmsPages
2
Academic year
2023
anon
Views
46
The Binary Max Heap Data Structure Full Pseudocode A form of data structure called the binary max heap is used to store elements ina fashion that allows for quick access to the largest element. The binary maxheap data structure's complete pseudocode is provided in this article so that youmay fully comprehend how it operates and how to include it into your owncode. We will maintain three variables: ● H: a container for our heap within an array. ● MaxSize: The maximum number of nodes in our heap as well as the sizeof this array. ● size: The size of our heap as it actually exists, which is always at mostmaxSize. Example To illustrate how these variables are used in practice, let's look at an example.Let's say that we are given a heap of size 9 that is kept in the first nine cells of a13-cell array H. The array's remaining cells might contain some values, butsince they are merely useless rubbish, we don't care about them. Only the topnine positions in the array are occupied by our heap. It's vital to remember that we only store the variables size and maxSize togetherwith the array H. This indicates that the tree is implicitly provided to us, and weare able to retrieve the corresponding value in the array as well as compute thenumber of the parent and two children of any node. The index of a node's left child, for instance, is “2 * i” and the index of a node'sright child, for example, is “2 * i + 1”. Sifting Element i Up The steps below are used to separate an element “i” ● We do the following actions when “i” is not the root (i.e., “i > 1”) and thevalue of the node is higher than the value of its parent: ○ Change the element's parent for it. ○ Repeat the process while setting “i” to equal the parent of “i”.
Sifting Element i Down The steps we use to narrow down an element “i” are as follows: ● By contrasting the value of “i” with the values of its two children, choosethe sifting direction first. ● Choose the largest child if “i” is smaller than one or both of its children. ● Replace “i” with the largest kid if it is not the largest among itself, its twochildren, and the others. ● With the element you just switched, repeat the procedure. Inserting a New Element We just place a new element with priority p in the bottom position of the heap, sift it up, and then insert it. Removing the Maximum Element We swap the maximum element with the last element in the heap, filter the new root element down, and finally remove the maximum element. To help you fully understand how the binary max heap data structure operates and how to incorporate it into your own code, we have supplied thebinary max heap data structure's complete pseudocode in this article. Thisknowledge will be invaluable in assisting you in comprehending and using thispotent data structure, regardless of your level of programming experience.
Binary Max Heap Data Structure Pseudocode
Please or to post comments