ARTICLE AD BOX
I'm learning about Heapsort using Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, in 6.2 of Chapter 6(Heapsort). Is talking about maintaining the heap property using a procedure called MAX-HEAPIFY(1). As I understand what the book is talking about, we use the procedure to make an input array called A, to convert it into a MAX-HEAP.
The code from the book: MAX-HEAPIFY pseudocode
The code uses the recursive approach, explaining how it works by finding the largest value.I don't have a problem with the code above, but when I try to write the code by myself to achieve the same purpose. I use the iterative approach, and I test my code with different inputs, but I'm not sure my code is working correctly or even achieves what suppose really to do.
My code:
vector<int> heapify(vector <int> A){ for(int i = 0; i < A.size(); i++){ int left = 2 * i + 1; int right = left + 1; int parent = floor((i-1)/2); if(left < A.size() && A[left] > A[i]){ swap(A[i],A[left]); } if(right < A.size() && A[right] > A[i]){ swap(A[i],A[right]); } if(parent >= 0 && A[i] > A[parent]){ swap(A[i],A[parent]); } } return A; }Description:
Input: an array of integers called A, not sorted. Random values. output: return the input array A, but in a Max-Heap. The main idea: I didn't use the recursive approach (to be honest, I still need to practice more to understand recursion hahahahaha). And I did use the iterative approach by checking what if the parent node is larger than the child nodes by a simple if statement.My Question is: How to know that my code is working correctly and could pass any test case?
Second Question: Is there a website that I could test my code on?
Important Question: Do I really understand what the MAX-Heapify really does? Please tell me if I'm not getting it in the right way.
Note: I use ChatGPT, but I didn't get what I really needed. So help me please.
Appendix: (1): the MAX-HEAPIFY(A, i) takes A as an input array and an index i into the array. When it's called, MAX-HEAPIFY assumes that the binary trees rooted at LEFT(i) and RIGHT(i) are max heaps, but that A[i] might be smaller than its children, thus violating the max-heap property.
