#include "expandinglist.h"
/ * Implement a heap-sort * /
/ * CREATE A Heap. Heapcreate (Heaplist Heapvar, (TypenAme) HeaPType, Int InitialSize, Int (* Compare_fn) (Const Void * A, Const Void * B))
Add an item to the heap. Heapadd (Heaplist Heapvar, (TypenAme) HeaPType, HeaPType Item
Return the value of an item in the head. Heapitem (Heaplist Heapvar, (Typename) HeaPType, HeaPType X)
Return the size of the heap. Heapsize (Heaplist Heapvar, (Typename) HeaPType
Return The Top Item on The Heap. (As modifi) Heaptop (Heaplist Heapvar, (Typename) HeaPType
Remove the Top Item from The Heap, Assign It To Itemvar. Heappop (Heaplist Heapvar, (Typename) HeaPType, HeaPType Itemvar
Destroy a heap with or weldestroy (Heaplist Heapvar, (Typename) HeaPType
* /
/ * The Heapsort Algorithm Works Works Well When Adding Data To a Listin Random ORDER, AND Removing It in A Sorted Order. Worst-CaseperFormance IS O (n log (n)).
As items are added, they are kept in a min-heap A min-heapis a binary tree in which every parent is less than either of itschildren It will always be full, so it can be implemented witha simple array Like such...:
a [] = {2, 5, 3, 13, 11, 17, 7}
- OR -
2 / / 5 3 / / / / / / / 13 11 17 7
When An ITEM IS Added, IT IS Stuck At the end of the tree andfloated up..
2 / / 5 3 / / / / / / / 13 11 17 7/4
- 4 floats up -
2 / / 5 3 / / / / / 4 11 17 7/13
2 / / 4 3 / / / / / / 5 11 17 7/13
When pulling items off the list in sorted order, pull off the topnode first, replace it with the last node, and have the new top nodesink down until it is less than either of its children. Make sure, when swapping it with a child, To swap it with the lesser child.2 <- / 4 3 / / / / / 5 11 17 7/13
13 / / 4 3 / / / / / / 5 11 17 7
3 / / 4 13 / / / / / 5 11 17 7
3 / / 4 7 / / / / / / 5 11 17 13
Do this until the tree is es Empty.
* /
#ifndef Heapsort_h # define Heapsort_H
#define heapsort_parent_ (x) (((x) == 0)? -1: ((x) -1) / 2) # define heapsort_lchild_ (x) ((x) 1) * 2-1) #define heapsort_rchild_ (x) (((x) 1) * 2)
#ifdef __stdc __ # define Heapsort_Compare_ (HeapVar, Type, A, B) / (* (INT (*) (Type *, Type *)) (Heapvar) -> Compare) (A, B)) # Else # define Heapsort_compare_ (Heapvar, Type, A, B) / ((* (Heapvar) (> Compare) (A, B)) # ENDIF
Struct Heaplist_ {xpandList List; int (* compare) ();
Typedef struct heaplist_ * heaplist;
#define HeapCreate (heapVar, type, initialSize, compare_fn) do {/ (heapVar) = (heapList) malloc (sizeof (struct heapList_)); (! (heapVar)) / if {/ fprintf (stderr, "Could not allocate memory For min-heap / n "); /} else {/ listcreate ((Heapvar) -> List, Type, (InitialSize)); / if (((HeapVar) -> list) {/ (HeapVar) -> Compare = INT (*) ()) (COMPARE_FN); /} /} /} While (0)
#define Heapdestroy (Heapvar, Type) Do {/ ListDestroy ((Heapvar), TYPE); / Free ((char *) (Heapvar);} while (0)
#DEfine Heapadd (Heapvar, Type, Item) DO {/ INT_I; / Type * _Head; / Type_x; / _head = Listheadptr ((Heapvar) -> List, Type); / / * make room in the list * / / ListAdditem ((Heapvar) -> List, Type, (Item)); / _X = (item); / / * float the new item up to the top * / / _i = listsize ((Heapvar) -> list, TYPE ) - 1; / while (_i && Heapsort_compare_ (Heapvar, Type, / (_Head) Heapsort_Parent_ (_ i), / & _X)> 0) {/ * (_HEAD _I) = * (_ Head Heapsort_Parent _ (_ i)); / _I = Heapsort_Parent _ (_ i); /} / * (_ head _i) = _x; /} while (0) #define HeapItem (Heapvar, Type, I) / ListItem ((Heapvar) -> List, Type, (i ))
#define Heapsize (Heapvar, Type) / Listsize ((Heapvar) -> List, Type
#define Heaptop (Heapvar, Type) / ListItem ((Heapvar) -> List, Type, 0)
#Define Heappop (Heapvar, Type, Itemvar) Do {/ INT_I, _Size; / Type *_Head; / Type_X; / / / * Get The Top Item * / / (Itemvar) = ListItem ((Heapvar) -> List , Type, 0); / / * Grab the last item * / / _x = Listitem ((Heapvar) -> List, Type, / ListSize ((HeapVar) -> List, Type) - 1); / ListremoveItems ((Heapvar ) -> list, type, 1); / / _i = 0; / _Size = Heapsize; / _Head = Listheadptr ((Heapvar) -> list, type); / / / * if i haven't Sunk paste the endweighs me * / / while (Heapsort_lchild _ (_ i) <_size) {/ if (Heapsort_rchild _ (_ i)> = _size) {/ / * only has left child, No Right Child * / / // (HeapVar, Type, / & _x, _Head Heapsort_LCHILD _ (_ i))> 0) {/ / * if Greater Than this One Child, Move THELD UP / AND SET I SO THAT X Gets Put in this child's place * / / * (_ head _i) = * (_ head heapsort_lchild _ (_ i)); / _i = heapsort_lchild _ (_ i); /} else {/ / * If Less Than! Leave I where it is / and exit so this x gets written * / / / / / / / / / / / / / / / / / / /} / /} /} else {/ * have} else {// * Have Both Children * / / f (Heapsort_Compare_ (Heapvar , TYPE, / _HEAD Heapsort_lchild _ (_ i), & _x)> 0 && / Heapsort_compare_ (Heapvar, Type, / _Head Heapsort_rchild _ (_ i), & _X)> 0) {/ / * if Both Children Are Greater Than X, WE ' Re Home * / / / /} else {/ / * swap with the smaller of the children * / / f (Heapsort_compare_ (Heapvar, Type, / _Head Heapsort_LCHILD _ (_ i), _Head Heapsort_rchild _ (_ i)) <0) {/ * (_ Head _i) =
* (_ head heapsort_lchild _ (_ i)); / _i = heapsort_lchild _ (_ i); /} else {/ * (_ head _i) = * (_ head heapsort_rchild _ (_ i)); / _i = Heapsort_rchild _ (_ i); /} /} /} /} / / / * Put x in its rightful place * / / * (_ head _i) = _x; /} while (0) #ENDIF
