Implement in ARM7 assembly language a max-heap. In the main function, open a file to read a sequence of unsorted integers. For the first input integer, create a root node (12 bytes), holding the integer in the first 4 bytes and two empty pointers, one for the left child node and the other for the right child node. For each of the remaining input integers, build a node N to hold the number (X) and insert the node to the tree such that (1) any descending nodes of N contain integers smaller than X and ancestral nodes of N contain integers equal or larger than X. Therefore, if X is larger than the root.data, then node N will become the new root and the old root becomes N's left child. (2) when N is inserted below a node M (because N.data < M.data), follow the following order: a. if M has two empty children, N is inserted as the left child of M; b. if M has only one empty child, for example the right child is empty, then N becomes the right child; c. if M has no empty children, N is inserted as M's the left child and M's original left child becomes N's right child. Implement the insert function with the following specification: Insert (heap, node), where heap is a pointer to the root node, and node is the node to be inserted. The Insert function should return the pointer to the root. Implement deleteMax function with the following specification: deleteMax(heap), where heap is a pointer to the root node of the heap. The deleteMax function should do the following: (1) return the maximum value stored in the heap, which is the root.data; (2) maintain the heap structure by recursively (i.e., continuously) percolating the vacancy down the binary tree to a leaf node and then removing the leaf node whose data is elevated to the parent node. Note: your deleteMax function does not have to be a recursive function. data Null or a Pointer to the left child node Null or a Pointer to the right child node
Implement in ARM7 assembly language a max-heap. In the main
function, open a file to read a sequence of unsorted integers. For the first input integer,
create a root node (12 bytes), holding the integer in the first 4 bytes and two empty
pointers, one for the left child node and the other for the right child node. For each of the
remaining input integers, build a node N to hold the number (X) and insert the node to the
tree such that
(1) any descending nodes of N contain integers smaller than X and ancestral nodes of
N contain integers equal or larger than X. Therefore, if X is larger than the
root.data, then node N will become the new root and the old root becomes N's
left child.
(2) when N is inserted below a node M (because N.data < M.data), follow the
following order:
a. if M has two empty children, N is inserted as the left child of M;
b. if M has only one empty child, for example the right child is empty, then
N becomes the right child;
c. if M has no empty children, N is inserted as M's the left child and M's
original left child becomes N's right child.
Implement the insert function with the following specification: Insert (heap, node),
where heap is a pointer to the root node, and node is the node to be inserted. The Insert
function should return the pointer to the root.
Implement deleteMax function with the following specification: deleteMax(heap), where
heap is a pointer to the root node of the heap. The deleteMax function should do the
following:
(1) return the maximum value stored in the heap, which is the root.data;
(2) maintain the heap structure by recursively (i.e., continuously) percolating the
vacancy down the binary tree to a leaf node and then removing the leaf node
whose data is elevated to the parent node. Note: your deleteMax function does
not have to be a recursive function.
| data | Null or a Pointer to the left child node | Null or a Pointer to the right child node |
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 2 images
