#ifndef _HEAP_H_
#define _HEAP_H_

/* This version implements the following detail mentioned in CLRS (2nd
 * ed), Section 6.5, pg. 139:
 *
 * "... elements of a priority queue correspond to objects in the
 * application. It is often necessary to determine which application
 * object corresponds to a given priority-queue element, and
 * vice-versa. When a heap is used to implement a priority queue,
 * therefore, we often need to store a handle to the corresponding
 * application object in each heap element. The exact makeup of the
 * handle (i.e., a pointer, an integer, etc.) depends on the
 * application. Similarly, we need to store a handle to the
 * corresponding heap element in each application object. Here, the
 * handle would typically be an array index. Because heap elements
 * change locations within the array during heap operations, an actual
 * implementation, upon relocating a heap element, would also have to
 * update the array index in the corresponding application object."
 *
 * These "handles" are initialised during insert() or build_heap() and
 * updated during swap_up and swap_down.
 *
 * In other words, during insert() / build_heap(), suppose h->heap[j] and
 * h->heap[k] are initialised to p and q. Then, h->index_in_heap[p] == j,
 * and h->index_in_heap[q] == k.
 * 
 * When h->heap[j] and h->heap[k] are swapped, h->index_in_heap[p] and
 * h->index_in_heap[q] also need to be swapped.
 *
 * This implementation uses one-based indexing as described in
 * SEDGEWICK AND WAYNE => h->heap[0] is unused; h->data[0] corresponds
 * to h->heap[1] and vice versa.
 */

typedef struct heap {
    size_t element_size; /* generic => need to store this */
    unsigned int num_allocated, num_used;
    void *data;          /* store the actual data elements */

    int *index_in_heap; /* see note from CLRS above */
    unsigned int *heap; /* heap only stores indices of the actual data
                         * elements stored in the data array */

    /* IMPORTANT: indexes correspond to heap array, not the data array */
    int (*comparator)(struct heap *, int, int); 
    bool free_data;
} HEAP;

typedef int (*COMPARATOR)(HEAP *, int, int);


/* init_heap creates an initially EMPTY heap with the specified capacity.
 * Elements are expected to be inserted one by one. */
extern int init_heap(HEAP *h, unsigned int capacity, size_t element_size,
                     COMPARATOR comparator);

/* build_heap creates a heap from an EXISTING array of specified length,
 * but will support subsequent insertions as well. */
extern int build_heap(HEAP *h, void *data, unsigned int num_elements,
                      size_t element_size, COMPARATOR comparator);

extern void free_heap(HEAP *h);

extern int insert(HEAP *h, void *x);
extern int delete_max(HEAP *h);
extern void increase_key(HEAP *h, int index_in_data);
extern void heapsort(HEAP *h);

#endif // _HEAP_H