I decided to improve my understanding of some algorithms and started studying with the book by Levitin. There was a problem with the implementation of the heap. Immediately quote the code, and then comment.
#include <iostream> #include <vector> #include <limits.h> void fixup(std::vector<int> &h){ int j, k, v, n; bool heap; n = h.size() - 1; for(int i = n/2; i >= 1; i--){ k = i; v = h[k]; heap = false; while(!heap && 2*k <= n){ j = 2*k; if(j < n) if(h[j] < h[j + 1]) j++; if(v >= h[j]) heap = true; else{ h[k] = h[j]; k = j; } } h[k] = v; } } int main(){ int size = 7; int in; std::vector<int> v(size); v[0] = INT_MAX; for(int i = 1; i <= size; i++){ std::cin >> v[i]; } for(int i = 1; i < size; i++){ std::cout << v[i] << " "; } fixup(v); std::cout << std::endl; for(int i = 1; i < size; i++){ std::cout << v[i] << " "; } } Here we consider each node except the leaves and check whether the heap property is satisfied for it. If not, we do the exchange of the node with its maximum descendant. The descendants of the node with index i in the array have indices 2i and 2i+1 , therefore in the internal while we stand on the left descendant 2i , and if it is less than 2i+1 , then the pointer j goes to this maximum descendant. Then the exchange is made, and I do not understand very well how this exchange is implemented.
The program does not work correctly: https://ideone.com/hcuvMA
After rebuilding the array into a heap, the nodes are not arranged as needed. The correct sequence is 10, 5, 7, 4, 2, 1.
Features of the implementation: the zero element of the array is not used; First, the array is filled with elements, and only then it is converted into a heap.
