Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //basic.h
- #ifndef BASIC_H
- #define BASIC_H
- #define _CRT_SECURE_NO_WARNINGS
- #include <stdlib.h>
- #include <stdio.h>
- #include <stdbool.h>
- #include <string.h>
- #include <stdint.h>
- typedef int element;
- extern element *toDynamic(const element v[], uint32_t n);
- extern bool isLeaf(uint32_t i, uint32_t heap_size);
- extern void swap(element *v, uint32_t a, uint32_t b);
- extern uint32_t left(uint32_t i);
- extern uint32_t right(uint32_t i);
- extern uint32_t parent(uint32_t i);
- extern element Max(element a, element b);
- extern void moveDown(element *v, uint32_t i, uint32_t heap_size);
- extern void moveUp(element *v, uint32_t i);
- extern void build_heap(element *v, uint32_t heap_size);
- extern void deleteNode(element *v, uint32_t i, uint32_t *heap_size);
- extern element *insertNode(element *v, element e, uint32_t *heap_size);
- extern bool isGreater(element lhs, element rhs);
- extern bool isLess(element lhs, element rhs);
- extern bool isEqual(element lhs, element rhs);
- extern void showHeap(element *v, uint32_t heap_size);
- extern bool isInvalidNode(uint32_t i, uint32_t heap_size);
- extern void printElement(element e);
- #endif /*!BASIC_H*/
- //basic.c
- element *toDynamic(const element v[], uint32_t n)
- {
- element *ret = (element*) malloc(n * sizeof(element));
- memcpy(ret, v, n * sizeof(element));
- return ret;
- }
- element *copyHeap(element *v, uint32_t heap_size)
- {
- element *copied = (element*)malloc((heap_size + 1) * sizeof(element));
- memcpy(copied, v, (heap_size + 1) * sizeof(element));
- return copied;
- }
- bool isLeaf(uint32_t i, uint32_t heap_size)
- {
- return i > parent(heap_size);
- }
- void swap(element *v, uint32_t a, uint32_t b)
- {
- element *temp = (element*) malloc(sizeof(element));
- memcpy(temp, &v[a], sizeof(element));
- memcpy(&v[a], &v[b], sizeof(element));
- memcpy(&v[b], temp, sizeof(element));
- }
- uint32_t left(uint32_t i)
- {
- return 2 * i;
- }
- uint32_t right(uint32_t i)
- {
- return 2 * i + 1;
- }
- uint32_t parent(uint32_t i)
- {
- return (i != 1 && i != 0) ? i / 2 : 0;
- }
- bool isGreater(element lhs, element rhs)
- {
- return lhs > rhs;
- }
- bool isEqual(element lhs, element rhs)
- {
- return lhs == rhs;
- }
- bool isLess(element lhs, element rhs)
- {
- return !isEqual(lhs, rhs) && !isGreater(lhs, rhs);
- }
- element Max(element a, element b)
- {
- if (isGreater(a, b)) return a;
- else if (isLess(a, b)) return b;
- return a;
- }
- void moveDown(element *v, uint32_t i, uint32_t heap_size)
- {
- if (isLeaf(i, heap_size)) return;
- uint32_t l = left(i), r = right(i);
- uint32_t u = l > r ? l : r;
- if (isLess(v[i], v[u]))
- {
- swap(v, i, u);
- moveDown(v, u, heap_size);
- }
- }
- void moveUp(element *v, uint32_t i)
- {
- while (i != 1 && (isGreater(v[i], v[parent(i)]) || isEqual(v[i], v[parent(i)])))
- {
- uint32_t father = parent(i);
- swap(v, i, father);
- i = father;
- }
- }
- void heapify(element *v, uint32_t i, uint32_t heap_size)
- {
- uint32_t l, r, largest = i;
- l = left(i);
- r = right(i);
- if ((l <= heap_size) && isGreater(v[l], v[r]))
- largest = l;
- if ((r <= heap_size) && isGreater(v[r], v[largest]))
- largest = r;
- if (largest != i)
- {
- swap(v, i, largest);
- heapify(v, largest, heap_size);
- }
- return;
- }
- void build_heap(element *v, uint32_t heap_size)
- {
- int i;
- for (i = heap_size / 2; i >= 1; i--)
- heapify(v, i, heap_size);
- }
- void deleteNode(element *v, uint32_t i, uint32_t *heap_size)
- {
- swap(v, 1, *heap_size);
- (*heap_size)--;
- heapify(v, 1, *heap_size);
- }
- void heapsort(element *v, uint32_t dim)
- {
- int i, heap_size = dim;
- for (i = dim; i >= 2; i--)
- {
- swap(v, 1, i);
- heapify(v, 1, --heap_size);
- }
- }
- element *insertNode(element *v, element e, uint32_t *heap_size)
- {
- (*heap_size)++;
- v = (element*) realloc(v, (*heap_size + 1) * sizeof(element));
- v[*heap_size] = e;
- moveUp(v, *heap_size);
- return v;
- }
- void printElement(element e)
- {
- printf("%d ", e);
- }
- bool isInvalidNode(uint32_t i, uint32_t heap_size)
- {
- return i > heap_size;
- }
- void quicksort(element *v, int first, int last)
- {
- if (first < last)
- {
- int i = first, j = last;
- element pivot = v[(first + last) / 2];
- do
- {
- while (isGreater(v[i], pivot)) i++;
- while (isLess(v[j], pivot)) j--;
- if (i <= j)
- {
- swap(v, i, j);
- i++, j--;
- }
- } while (i <= j);
- quicksort(v, first, j);
- quicksort(v, i, last);
- }
- }
- void showHeap(element *v, uint32_t heap_size)
- {
- element *copied = copyHeap(v, heap_size);
- quicksort(copied, 1, heap_size);
- for (uint32_t i = 1; i <= heap_size; i++) printElement(copied[i]);
- free(copied);
- }
- int main(void)
- {
- return EXIT_SUCCESS;
- }
Advertisement
Add Comment
Please, Sign In to add comment