MHB Proving Correctness of Heap Building Algorithm

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Algorithm
AI Thread Summary
The discussion centers on proving the correctness of the BUILDHEAP algorithm, specifically focusing on the assertion that at the start of each iteration of the for loop, every node from i+1 to n is the root of a max-heap. It is emphasized that proving this statement is sufficient for establishing the overall correctness of the algorithm. The reasoning is that if each node satisfies the max-heap property, then the entire structure will also satisfy it after the heapify process is applied. The mention of the "sift down" algorithm clarifies that this method effectively transforms a subtree into a heap, starting from the root, which simplifies the proof process. The participants agree that the correctness of the heapify operation is crucial, as it ensures that the properties of the heap are maintained throughout the iterations.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
Hello! (Nerd)

We are given the following algorithm:

Code:
1.BUILDHEAP(A) 
2.    for (i=floor(size(A))/2; i>=0; i--)
3.          HEAPIFY(A,i);

according to my notes, we could prove its correctness, proving the following sentence:

At the beginning of each iteration of the for loop at the lines 2-3, each node $i+1, i+2, \dots, n $ is the root of a max-heap.

Could you explain me why it suffices to prove the above sentence?

Also, how could we prove it? (Thinking)
 
Technology news on Phys.org
You ignored "heapify". Assuming this is the standard "sift down" algorithm, I don't see that there's much of anything to prove. Sift down produces a heap, starting at the "root".
 
Thread 'Is this public key encryption?'
I've tried to intuit public key encryption but never quite managed. But this seems to wrap it up in a bow. This seems to be a very elegant way of transmitting a message publicly that only the sender and receiver can decipher. Is this how PKE works? No, it cant be. In the above case, the requester knows the target's "secret" key - because they have his ID, and therefore knows his birthdate.
Thread 'Project Documentation'
Trying to package up a small bank account manager project that I have been tempering on for a while. One that is certainly worth something to me. Although I have created methods to whip up quick documents with all fields and properties. I would like something better to reference in order to express the mechanical functions. It is unclear to me about any standardized format for code documentation that exists. I have tried object orientated diagrams with shapes to try and express the...

Similar threads

Back
Top