0
What is the running time of transforming an arbitrary array into heap?
Wiki User
∙ 8y ago
Building a heap from an arbitrary array takes O(n) time for an array of n elements.
Wiki User
∙ 8y ago
Add your answer:
Earn +20 pts
Is an array that is in sorted order a min-heap?
Yes, an array that is in sorted order is considered a min-heap because the smallest item in the array is the root. Also, the rest of the items in the array will gradually get bigger from the root until the end of the array.
What is the running time of heapsort on an array A of length n that is already sorted in increasing order?
The running time of HEAPSORT on an array A of length n that is already sorted in increasing order is (n lg n) because even though it is already sorted, it will be transformed back into a heap andsorted.The running time of HEAPSORT on an array A of length n that is sorted in decreasing order willbe (n lg n). This occurs because even though the heap will be built in linear time, every time themax element is removed and the HEAPIFY is called it will cover the full height of the tree
How do you sort the given contents of an array?
You would sort the given elements of an array by a bubble sort or heap sort code!!
Implementation of priority Queue using Heap?
Now let's consider how to implement priority queues using a heap. The standard approach is to use an array (or an ArrayList), starting at position 1 (instead of 0), where each item in the array corresponds to one node in the heap:The root of the heap is always in array[1].Its left child is in array[2].Its right child is in array[3].In general, if a node is in array[k], then its left child is in array[k*2], and its right child is in array[k*2 + 1].If a node is in array[k], then its parent is in array[k/2] (using integer division, so that if k is odd, then the result is truncated; e.g., 3/2 = 1).Here's an example, showing both the conceptual heap (the binary tree), and its array representation: Note that the heap's "shape" property guarantees that there are never any "holes" in the array.The operations that create an empty heap and return the size of the heap are quite straightforward; below we discuss the insert and removeMax operations.Implementing insertWhen a new value is inserted into a priority queue, we need to: Add the value so that the heap still has the order and shape properties, andDo it efficiently!The way to achieve these goals is as follows: Add the new value at the end of the array; that corresponds to adding it as a new rightmost leaf in the tree (or, if the tree was a complete binary tree, i.e., all leaves were at the same depth d, then that corresponds to adding a new leaf at depth d+1).Step 1 above ensures that the heap still has the shapeproperty; however, it may not have the order property. We can check that by comparing the new value to the value in its parent. If the parent is smaller, we swap the values, and we continue this check-and-swap procedure up the tree until we find that the order property holds, or we get to the root.Here's a series of pictures to illustrate inserting the value 34 into a heap:
What will be the difference in running time of the heap sort algorithm if you start to apply heap sort with an array elements rather than max heap elements?
The heap sort algorithm is as follows: 1. Call the build_max_heap() function. 2. Swap the first and last elements of the max heap. 3. Reduce the heap by one element (elements that follow the heap are in sorted order). 4. Call the sift_down() function. 5. Goto step 2 unless the heap has one element. The build_max_heap() function creates the max heap and takes linear time, O(n). The sift_down() function moves the first element in the heap into its correct index, thus restoring the max heap property. This takes O(log(n)) and is called n times, so takes O(n * log(n)). The complete algorithm therefore equates to O(n + n * log(n)). If you start with a max heap rather than an unsorted array, there will be no difference in the runtime because the build_max_heap() function will still take O(n) time to complete. However, the mere fact you are starting with a max heap means you must have built that heap prior to calling the heap sort algorithm, so you've actually increased the overall runtime by an extra O(n), thus taking O(2n * log(n)) in total.
Is an array that is in sorted order a min heap?
Yes, an array that is in sorted order is considered a min-heap because the smallest item in the array is the root. Also, the rest of the items in the array will gradually get bigger from the root until the end of the array.
Is an array that is in sorted order a min-heap?
Yes, an array that is in sorted order is considered a min-heap because the smallest item in the array is the root. Also, the rest of the items in the array will gradually get bigger from the root until the end of the array.
How do you sort the given contents of an array?
You would sort the given elements of an array by a bubble sort or heap sort code!!
What is the running time of heapsort on an array A of length n that is already sorted in increasing order?
The running time of HEAPSORT on an array A of length n that is already sorted in increasing order is (n lg n) because even though it is already sorted, it will be transformed back into a heap andsorted.The running time of HEAPSORT on an array A of length n that is sorted in decreasing order willbe (n lg n). This occurs because even though the heap will be built in linear time, every time themax element is removed and the HEAPIFY is called it will cover the full height of the tree
How do you locate memory in array?
The array name is a reference to the start address of the array, so simply take its address. int a[10]; int* p1 = &a; If the array is allocated on the heap, then there is no name (all allocations on the heap are anonymous). However, you don't need a name since you already know the address: int* p2 = malloc (10 * sizeof (int));
Implementation of priority Queue using Heap?
Now let's consider how to implement priority queues using a heap. The standard approach is to use an array (or an ArrayList), starting at position 1 (instead of 0), where each item in the array corresponds to one node in the heap:The root of the heap is always in array[1].Its left child is in array[2].Its right child is in array[3].In general, if a node is in array[k], then its left child is in array[k*2], and its right child is in array[k*2 + 1].If a node is in array[k], then its parent is in array[k/2] (using integer division, so that if k is odd, then the result is truncated; e.g., 3/2 = 1).Here's an example, showing both the conceptual heap (the binary tree), and its array representation: Note that the heap's "shape" property guarantees that there are never any "holes" in the array.The operations that create an empty heap and return the size of the heap are quite straightforward; below we discuss the insert and removeMax operations.Implementing insertWhen a new value is inserted into a priority queue, we need to: Add the value so that the heap still has the order and shape properties, andDo it efficiently!The way to achieve these goals is as follows: Add the new value at the end of the array; that corresponds to adding it as a new rightmost leaf in the tree (or, if the tree was a complete binary tree, i.e., all leaves were at the same depth d, then that corresponds to adding a new leaf at depth d+1).Step 1 above ensures that the heap still has the shapeproperty; however, it may not have the order property. We can check that by comparing the new value to the value in its parent. If the parent is smaller, we swap the values, and we continue this check-and-swap procedure up the tree until we find that the order property holds, or we get to the root.Here's a series of pictures to illustrate inserting the value 34 into a heap:
What will be the difference in running time of the heap sort algorithm if you start to apply heap sort with an array elements rather than max heap elements?
The heap sort algorithm is as follows: 1. Call the build_max_heap() function. 2. Swap the first and last elements of the max heap. 3. Reduce the heap by one element (elements that follow the heap are in sorted order). 4. Call the sift_down() function. 5. Goto step 2 unless the heap has one element. The build_max_heap() function creates the max heap and takes linear time, O(n). The sift_down() function moves the first element in the heap into its correct index, thus restoring the max heap property. This takes O(log(n)) and is called n times, so takes O(n * log(n)). The complete algorithm therefore equates to O(n + n * log(n)). If you start with a max heap rather than an unsorted array, there will be no difference in the runtime because the build_max_heap() function will still take O(n) time to complete. However, the mere fact you are starting with a max heap means you must have built that heap prior to calling the heap sort algorithm, so you've actually increased the overall runtime by an extra O(n), thus taking O(2n * log(n)) in total.
Can you change the base address of an array during run time?
If the compiler allocated the array at compile time, or if the array was automatically allocated as a local variable, then no, you cannot change its base address at run time. If you allocated the array at run time from the heap, you can change its base address by allocating a new array, copying the old elements from old to new and deleting the old array.
Are arrays objects?
Yes. Arrays are objects in Java that store multiple variables of the same type. Arrays can hold either primitives or object references, but the array itself will always be an object on the heap, even if the array is declared to hold primitive elements. In other words, there is no such thing as a primitive array, but you can make an array of primitives
When is memory allocated when declaring an array in C plus plus?
It depends how the array is declared (fixed size or variable size) and where it is declared (global scope or local scope). If the array is declared in global scope (outside a function) and is fixed size, it will be allocated in static memory. If it is variable size, the pointer is stored in static memory while the array itself is allocated on the heap. The pointer in static memory points to the start address of the array in heap memory. If the array is declared in local scope (inside a function) and is fixed size, it will be allocated on the stack in whichever thread the function was called. If it is variable size, the local pointer is stored on the stack while the array is allocated on the heap. The pointer will fall from scope when the function returns so the array must not be allowed to outlive the function in which the pointer is declared. If the array must outlive the function that allocates the array, the pointer must be declared at a higher scope in the call stack and must be passed by reference to or returned by value from the function that allocates the array. If you provide your own memory manager, however, an array may be allocated wherever the memory manager's memory pool is allocated, be it in static memory, the stack or the heap. A memory manager essentially allocates an array of bytes which you can then utilise as you see fit (the array of bytes will be allocated as per the previous description for arrays in general).
What is a heap dump?
A heap dump is a snapshot of the memory heap of a running Java application, captured at a specific point in time. It provides detailed information about the various objects and their sizes in memory, helping developers analyze memory usage, detect memory leaks, and optimize application performance.
How can I fix Stack overflow at line 156?
A stack overflow is usually the cause of an array that is too small to be able to hold the intended data. To fix a stack overflow, the array must be locally declared (this means not dynamically allocated off of the heap) and then you must change the amount of "slots" in the array to something that is big enough to hold your data.
