Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <stdbool.h>
- void swap(double *u, double *v);
- void fix_heap(double *V, size_t node, size_t N);
- size_t heap_right(size_t index, size_t N);
- size_t heap_left(size_t index, size_t N);
- size_t parent(size_t index);
- bool is_leaf(size_t index, size_t N);
- void heapify(double *V, size_t node, size_t N);
- int main(void)
- {
- size_t N;
- scanf("%zu", &N);
- double *V = (double *)malloc(sizeof(double) * N);
- for (size_t i = 0; i < N; i++)
- scanf("%ld", &V[i]);
- fix_heap(V, 0, N);
- printf("[ ");
- for (size_t i = 0; i < N; i++)
- printf("%ld ", V[i]);
- printf("]");
- free(V);
- return 0;
- }
- void swap(double *u, double *v)
- {
- double temp = *u;
- *u = *v;
- *v = temp;
- }
- size_t heap_left(size_t index, size_t N)
- {
- const size_t left = 2 * index + 1;
- return left < N ? left : -1;
- }
- size_t heap_right(size_t index, size_t N)
- {
- const size_t right = 2 * index + 2;
- return right < N ? right : -1;
- }
- size_t parent(size_t index)
- {
- return (index - 1) / 2;
- }
- bool is_leaf(size_t index, size_t N)
- {
- return heap_left(index, N) != -1;
- }
- void fix_heap(double *V, size_t node, size_t N)
- {
- // Exit if the node is a leaf
- if (is_leaf(node, N))
- return;
- // Largest children of node
- size_t largest;
- size_t left = heap_left(node, N),
- right = heap_right(node, N);
- if (left == -1 || right == -1)
- return;
- if (V[left] >= V[right])
- largest = left;
- else
- largest = right;
- // If son has a larger value swaps pushing the highest value top
- if (V[node] < V[largest])
- {
- // Swap
- swap(&V[node], &V[largest]);
- // Recursion
- fix_heap(V, largest, N);
- }
- }
- void heapify(double *V, size_t node, size_t N)
- {
- // If we are done with the heap then return
- if (node == N || node == -1)
- return;
- // Right and left recursive heapify
- heapify(V, heap_left(node, N), N);
- heapify(V, heap_right(node, N), N);
- // Positioning correctly the root with fixHeap
- fix_heap(V, node, N);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement