/* TSP priority_queue.c Implementation of a heap / priority queue abstract data type, adjusted for complete records with key and data fields. */ /* Copyright 2003-2020 by Steven S. Skiena; all rights reserved. Permission is granted for use in non-commerical applications provided this copyright notice remains intact and unchanged. These programs appear in my books: "The Algorithm Design Manual" by Steven Skiena, second edition, Springer, London 2008. See out website www.algorist.com for additional information or https://www.amazon.com/exec/obidos/ASIN/1848000693/thealgorith01-20 "Programming Challenges: The Programming Contest Training Manual" by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003. See our website www.programming-challenges.com for additional information, or https://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/ */ #include #include #include "tsp-pq.h" /* [[[ tsp_pq_init_cut */ void pq_init(priority_queue *q) { q->n = 0; } /* ]]] */ /* [[[ tsp_pq_parent_cut */ int pq_parent(int n) { if (n == 1) { return(-1); } return((int) n/2); /* implicitly take floor(n/2) */ } /* ]]] */ /* [[[ tsp_pq_young_child */ int pq_young_child(int n) { return(2 * n); } /* ]]] */ void pq_swap(priority_queue *q, int i, int j) { tsp_solution temp; /* placeholder */ temp = q->q[i]; q->q[i] = q->q[j]; q->q[j] = temp; } /* [[[ tsp_bubble_up_cut */ void bubble_up(priority_queue *q, int p) { if (pq_parent(p) == -1) { return; /* at root of heap, no parent */ } if (q->q[pq_parent(p)].cost > q->q[p].cost ) { pq_swap(q, p, pq_parent(p)); bubble_up(q, pq_parent(p)); } } /* ]]] */ /* [[[ tsp_bubble_down_cut */ void bubble_down(priority_queue *q, int p) { int c; /* child index */ int i; /* counter */ int min_index; /* index of lightest child */ c = pq_young_child(p); min_index = p; for (i = 0; i <= 1; i++) { if ((c + i) <= q->n) { if (q->q[min_index].cost > q->q[c + i].cost) { min_index = c + i; } } } if (min_index != p) { pq_swap(q, p, min_index); bubble_down(q, min_index); } } /* ]]] */ /* [[[ tsp_pq_insert_cut */ void pq_insert(priority_queue *q, tsp_solution *x) { if (q->n >= PQ_SIZE) { printf("Warning: priority queue overflow insert x=%7.1f\n", x->cost); } else { q->n = (q->n) + 1; q->q[q->n] = *x; bubble_up(q, q->n); } } /* ]]] */ /* [[[ tsp_extract_min */ tsp_solution extract_min(priority_queue *q) { tsp_solution min; /* minimum value */ if (q->n <= 0) printf("Warning: empty priority queue.\n"); min = q->q[1]; q->q[1] = q->q[q->n]; q->n = q->n - 1; bubble_down(q, 1); return(min); } /* ]]] */ tsp_solution top_pq(priority_queue *q) { if (q->n <= 0) { printf("Warning: empty priority queue.\n"); } return(q->q[1]); } int empty_pq(priority_queue *q) { return (q->n <= 0); } void print_pq(priority_queue *q) { int i; /* counter */ for (i = 1; i <= q->n; i++) { printf("%7.1f ", q->q[i].cost); } printf("\n"); } /* [[[ tsp_make_heap2_cut */ void make_heap_fast(priority_queue *q, tsp_solution s[], int n) { int i; /* counter */ q->n = n; for (i = 0; i < n; i++) { q->q[i + 1] = s[i]; } for (i = q->n/2; i >= 1; i--) { bubble_down(q, i); } } /* ]]] */ /* [[[ tsp_make_heap_cut */ void make_heap(priority_queue *q, tsp_solution s[], int n) { int i; /* counter */ pq_init(q); for (i = 0; i < n; i++) { pq_insert(q, &s[i]); } } /* ]]] */ /* [[[ tsp_heap_compare_cut */ int heap_compare(priority_queue *q, int i, int count, int x) { if ((count <= 0) || (i > q->n)) { return(count); } if (q->q[i].cost < x) { count = heap_compare(q, pq_young_child(i), count-1, x); count = heap_compare(q, pq_young_child(i)+1, count, x); } return(count); } /* ]]] */