|
Packit Service |
75d76b |
/*
|
|
Packit Service |
75d76b |
* Copyright (c) 2020 Red Hat, Inc.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* This program is free software; you can redistribute it and/or
|
|
Packit Service |
75d76b |
* modify it under the terms of the GNU General Public License
|
|
Packit Service |
75d76b |
* as published by the Free Software Foundation; either version 2
|
|
Packit Service |
75d76b |
* of the License, or (at your option) any later version.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* This program is distributed in the hope that it will be useful,
|
|
Packit Service |
75d76b |
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
|
Packit Service |
75d76b |
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
|
Packit Service |
75d76b |
* GNU General Public License for more details.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* You should have received a copy of the GNU General Public License
|
|
Packit Service |
75d76b |
* along with this program; if not, write to the Free Software
|
|
Packit Service |
75d76b |
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
|
|
Packit Service |
75d76b |
* 02110-1301, USA.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* $Id: //eng/vdo-releases/aluminum/src/c++/vdo/base/heap.h#2 $
|
|
Packit Service |
75d76b |
*/
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
#ifndef HEAP_H
|
|
Packit Service |
75d76b |
#define HEAP_H
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
#include "common.h"
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* Prototype for functions which compare two array elements. All the time
|
|
Packit Service |
75d76b |
* complexity claims in this module assume this operation has O(1) time
|
|
Packit Service |
75d76b |
* complexity.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @param item1 The first element to compare
|
|
Packit Service |
75d76b |
* @param item2 The second element to compare
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @return An integer which is less than, equal to, or greater than 0
|
|
Packit Service |
75d76b |
* depending on whether item1 is less than, equal to, or greater
|
|
Packit Service |
75d76b |
* than item2, respectively
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
typedef int HeapComparator(const void *item1, const void *item2);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* Prototype for functions which swap two array elements.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @param item1 The first element to swap
|
|
Packit Service |
75d76b |
* @param item2 The second element to swap
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
typedef void HeapSwapper(void *item1, void *item2);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* A heap array can be any array of fixed-length elements in which the heap
|
|
Packit Service |
75d76b |
* invariant can be established. In a max-heap, every child of a node must be
|
|
Packit Service |
75d76b |
* at least as large as its children. Once that invariant is established in an
|
|
Packit Service |
75d76b |
* array by calling buildHeap(), all the other heap operations may be used on
|
|
Packit Service |
75d76b |
* that array.
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
typedef struct heap {
|
|
Packit Service |
75d76b |
/** the 1-based array of heap elements (nodes) */
|
|
Packit Service |
75d76b |
byte *array;
|
|
Packit Service |
75d76b |
/** the function to use to compare two elements */
|
|
Packit Service |
75d76b |
HeapComparator *comparator;
|
|
Packit Service |
75d76b |
/** the function to use to swap two elements */
|
|
Packit Service |
75d76b |
HeapSwapper *swapper;
|
|
Packit Service |
75d76b |
/** the maximum number of elements that can be stored */
|
|
Packit Service |
75d76b |
size_t capacity;
|
|
Packit Service |
75d76b |
/** the size of every element (in bytes) */
|
|
Packit Service |
75d76b |
size_t elementSize;
|
|
Packit Service |
75d76b |
/** the current number of elements in the heap */
|
|
Packit Service |
75d76b |
size_t count;
|
|
Packit Service |
75d76b |
} Heap;
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* Initialize an binary heap by wrapping it around an array of elements.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* The heap will not own the array it wraps. Use buildHeap() subsequently to
|
|
Packit Service |
75d76b |
* arrange any elements contained in the array into a valid heap.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @param heap The heap to initialize
|
|
Packit Service |
75d76b |
* @param comparator The function to use to compare two heap elements
|
|
Packit Service |
75d76b |
* @param swapper The function to use to swap two heap elements
|
|
Packit Service |
75d76b |
* @param array The array of elements (not modified by this call)
|
|
Packit Service |
75d76b |
* @param capacity The maximum number of elements which fit in the array
|
|
Packit Service |
75d76b |
* @param elementSize The size of every array element, in bytes
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
void initializeHeap(Heap *heap,
|
|
Packit Service |
75d76b |
HeapComparator *comparator,
|
|
Packit Service |
75d76b |
HeapSwapper *swapper,
|
|
Packit Service |
75d76b |
void *array,
|
|
Packit Service |
75d76b |
size_t capacity,
|
|
Packit Service |
75d76b |
size_t elementSize);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* Build a max-heap in place in an array (heapify it) by re-ordering the
|
|
Packit Service |
75d76b |
* elements to establish the heap invariant. Before calling this function,
|
|
Packit Service |
75d76b |
* first copy the elements to be arranged into a heap into the array that was
|
|
Packit Service |
75d76b |
* passed to initializeHeap(). This operation has O(N) time complexity in the
|
|
Packit Service |
75d76b |
* number of elements in the array.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @param heap The heap to build
|
|
Packit Service |
75d76b |
* @param count The number of elements in the array to build into a heap
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
void buildHeap(Heap *heap, size_t count);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* Check whether the heap is currently empty.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @param heap The heap to query
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @return true if there are no elements in the heap
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
static inline bool isHeapEmpty(const Heap *heap)
|
|
Packit Service |
75d76b |
{
|
|
Packit Service |
75d76b |
return (heap->count == 0);
|
|
Packit Service |
75d76b |
}
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* Remove the largest element from the top of the heap and restore the heap
|
|
Packit Service |
75d76b |
* invariant on the remaining elements. This operation has O(log2(N)) time
|
|
Packit Service |
75d76b |
* complexity.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @param [in] heap The heap to modify
|
|
Packit Service |
75d76b |
* @param [out] elementPtr A pointer to receive the largest element (may be
|
|
Packit Service |
75d76b |
* NULL if the caller just wishes to discard it)
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @return false if the heap was empty, so no element was removed
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
bool popMaxHeapElement(Heap *heap, void *elementPtr);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* Sort the elements contained in a heap.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* This function re-orders the elements contained in the heap to a sorted
|
|
Packit Service |
75d76b |
* array in-place by repeatedly popping the maximum element off the heap and
|
|
Packit Service |
75d76b |
* moving it to the spot vacated at the end of the heap array. When the
|
|
Packit Service |
75d76b |
* function returns, the heap will be empty and the array will contain the
|
|
Packit Service |
75d76b |
* elements in sorted order, from heap minimum to heap maximum. The sort is
|
|
Packit Service |
75d76b |
* unstable--relative ordering of equal keys is not preserved. This operation
|
|
Packit Service |
75d76b |
* has O(N*log2(N)) time complexity.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @param heap The heap containing the elements to sort
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @return the number of elements that were sorted
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
size_t sortHeap(Heap *heap);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
/**
|
|
Packit Service |
75d76b |
* Gets the next sorted heap element and returns a pointer to it, in O(log2(N))
|
|
Packit Service |
75d76b |
* time.
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @param heap The heap to sort one more step
|
|
Packit Service |
75d76b |
*
|
|
Packit Service |
75d76b |
* @return a pointer to the element sorted, or NULL if already fully sorted.
|
|
Packit Service |
75d76b |
**/
|
|
Packit Service |
75d76b |
void *sortNextHeapElement(Heap *heap);
|
|
Packit Service |
75d76b |
|
|
Packit Service |
75d76b |
#endif /* HEAP_H */
|