University:
University of California, San Diego
Course:
CSE 100/101 | Data Structures and Algorithms
Academic year:

2023
Views:

434

Pages:

2
Author:

anon

The Binary Max Heap Data Structure Full Pseudocode A form of data structure called the binary max heap is used to store elements in a fashion that allows for quick access to the largest element. The binary max heap data structure's complete pseudocode is provided in this article so that you may fully comprehend how it operates and how to include it into your own code. 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 size of this array. ● size: The size of our heap as it actually exists, which is always at most maxSize. 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 a 13-cell array H. The array's remaining cells might contain some values, but since they are merely useless rubbish, we don't care about them. Only the top nine positions in the array are occupied by our heap. It's vital to remember that we only store the variables size and maxSize together with the array H. This indicates that the tree is implicitly provided to us, and we are able to retrieve the corresponding value in the array as well as compute the number 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's right 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 the value 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, choose the 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 two children, 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 the binary max heap data structure's complete pseudocode in this article. This knowledge will be invaluable in assisting you in comprehending and using this potent data structure, regardless of your level of programming experience.