Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <malloc.h>
- struct heap {
- int size;
- int ind;
- int *mas;
- };
- heap *nheap(int size) {
- heap *h = (heap *) malloc(sizeof(heap));
- h->ind = 0;
- h->size = size;
- h->mas = (int *) (malloc(size*sizeof(int)));
- return h;
- }
- void sifting(heap *h, int ind) {
- int *mas = h->mas;
- if (ind == 0) {
- return;
- }
- if (ind & 1) {
- if (mas[ind] > mas[(ind - 1)/2]) {
- int t = mas[ind];
- mas[ind] = mas[(ind - 1)/2];
- mas[(ind - 1)/2] = t;
- }
- sifting(h, (ind - 1)/2);
- } else {
- if (mas[ind] > mas[ind/2 - 1]) {
- int t = mas[ind];
- mas[ind] = mas[ind/2 - 1];
- mas[ind/2 - 1] = t;
- }
- sifting(h, ind/2 - 1);
- }
- }
- void add_el_to_heap(heap *h, int element) {
- if (h->ind >= h->size) {
- h->size *= 2;
- int *nmas = (int *) realloc(h->mas, h->size*sizeof(int));
- if (nmas) {
- h->mas = nmas;
- }
- }
- h->mas[h->ind] = element;
- sifting(h, h->ind++);
- }
- void heapify(heap *h, int ind) {
- if (ind >= h->ind/2) {
- return;
- }
- int *mas = h->mas;
- int el = mas[ind];
- if (2*ind + 2 == h->ind) {
- if (el < mas[2*ind + 2]) {
- mas[ind] = mas[2*ind + 2];
- mas[2*ind + 2] = el;
- }
- } else {
- int maxind = (mas[2*ind + 1] > mas[2*ind + 2]) ? (2*ind + 1) : (2*ind + 2);
- mas[ind] = mas[maxind];
- mas[maxind] = el;
- }
- }
- int delmax(heap *h){
- if(h->ind == 0){
- return 0;
- }
- int *mas = h->mas;
- int max = mas[0];
- mas[0] = mas[--h->ind];
- heapify(h, 0);
- return max;
- }
- void printheap(heap *h) {
- for (int i = 0; i < h->ind; i++) {
- printf("%d ", h->mas[i]);
- }
- printf("\n");
- }
- int main() {
- heap *h = nheap(8);
- add_el_to_heap(h, 5);
- add_el_to_heap(h, 4);
- add_el_to_heap(h, 8);
- add_el_to_heap(h, 3);
- add_el_to_heap(h, 1);
- add_el_to_heap(h, 0);
- add_el_to_heap(h, 16);
- add_el_to_heap(h, 4);
- add_el_to_heap(h, 12);
- for(int i = 0; i < 9; i++){
- printf("%d ", delmax(h));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment