Как реализовать структуру данных кучи с помощью C ++?
Используя этот простой пример двоичной кучи. Как бы я реализовать эту структуру данных с помощью кода C ++.
1
/ \
3 6
/\ /\
5 9 8
Кроме того, как полезна эта структура данных, кроме возможности получить легкий доступ к максимальным или минимальным значениям в массиве?
Пример взят по следующей ссылке: http://www.algolist.net/Data_structures/Binary_heap
Решение
Вот моя самая простая реализация C ++ для кучи. Код хорошо прокомментирован.
/*
Usage:
heap Heap;
Heap.clear();
Heap.insert(value);
Heap.remove();
Heap.print();
*/
struct heap {
int myarray[NN+1]; // myarray to store the numbers as heap, 1 indexed
int n; // the number of nodes in my array
heap() { // constructor
clear(); // we clear the heap
}
void clear() { // initialize the heap
n = 0; // initially there are no nodes in the heap
}
void insert( int K ) { // inserting an element K in the heap
if( n == NN ) { // the heap is full
printf("cannot insert any more element, the heap is full\n");
return;
}
++n; // so, we have a new element, we increased n before adding
// the element because we start from index 1
myarray[n] = K; // inserted the element at the rightmost position
int p = n; // for keeping the current position
while( p > 1 ) { // p = 1 means we are on the root, and its a heap
int pr = p / 2; // pr is the parent of p
if( myarray[pr] > myarray[p] ) { // parent is greater than child
swap( myarray[pr], myarray[p] );
p = pr; // now the new position of the current element is pr
} else break; // otherwise its a heap, so we can stop here
}
}
int remove() { // removing the minimum element from the heap
if( n == 0 ) { // is the heap is empty
printf("The heap is empty, cannot delete.\n");
return -1;
}
int K = myarray[1]; // first element in the heap is the minimum
myarray[1] = myarray[n]; // brought the last element in 1st position
n--; // as we removed one element, now we need to maintain the heap
int p = 1; // as we moved the rightmost element in index 1
while( 2 * p <= n ) { // means p has at least one child, if 2*p > n
// we are sure that p is in the last level
int ch = 2 * p; // contains the index of the child
if( 2 * p + 1 <= n ) { // right child exists
if( myarray[ch] > myarray[ch+1] ) // right child is smaller
// than left child
ch++; // ch contains the index of the right child
}
if( myarray[p] > myarray[ch] ) { // so, current node is larger
// than its child
swap( myarray[p], myarray[ch] );
p = ch; // new position of the current element
} else break; //current node is smaller than its children, so heap
}
return K; // as we stored the minimum element in K
}
void print() { // printing the heap
printf("Number of elements: %d\n", n);
for( int i = 1; i <= n; i++ ) printf("%d ", myarray[i]);
printf("\n");
}
// Time: O(nlogn)
// Extra space: O(1) as we will pass the input array as res here
void heapSort(int* res) {
for(int i = 0, len = n; i < len; ++i) {
res[i] = remove();
}
}
};
Другие решения
Я пишу ниже Java реализация может помочь вам написать код в c++;
import java.util.Arrays;
/**
* Min heap implementation, also caters to duplicate
*/
public class MinHeap {`
private int capacity = 10;
private int size;
int[] items;
public MinHeap() {
items = new int[capacity];
size = 0;
}
public void ensureExtraCapacity() {
if (size == capacity) {
items = Arrays.copyOf(items, capacity * 2);
capacity *= 2;
}
}
private int getLeftChildIndex(int index) {
return 2 * index + 1;
}
private int getRightChildIndex(int index) {
return 2 * index + 2;
}
private int getParentIndex(int index) {
return (index - 1) / 2;
}
private boolean hasLeftChild(int index) {
return size > getLeftChildIndex(index);
}
private boolean hasRightChild(int index) {
return size > getRightChildIndex(index);
}
private boolean hasParent(int index) {
if(index == 0)
return false;
return getParentIndex(index) >= 0;
}
private int leftChild(int index) {
return items[getLeftChildIndex(index)];
}
private int rightChild(int index) {
return items[getRightChildIndex(index)];
}
private int parent(int index) {
return items[getParentIndex(index)];
}
private void swapValues(int index1, int index2) {
int temp = items[index1];
items[index1] = items[index2];
items[index2] = temp;
}
public int peek() {
if (size == 0) throw new IllegalStateException();
return items[0];
}
public int poll() {
if (size == 0) throw new IllegalStateException();
int polled = items[0];
items[0] = items[size - 1];
size--;
heapifyDown();
return polled;
}
public void add(int item) {
ensureExtraCapacity();
items[size] = item;
size++;
heapifyUp();
}
private void heapifyUp() {
int index = size - 1;
while (hasParent(index) && parent(index) > items[index]) {
swapValues(index, getParentIndex(index));
index = getParentIndex(index);
}
}
private void heapifyDown() {
int index = 0;
while (hasLeftChild(index)) {
int minimumChildIndex = getLeftChildIndex(index);
if (hasRightChild(index) && rightChild(index) < leftChild(index))
minimumChildIndex = getRightChildIndex(index);
if (items[index] < items[minimumChildIndex]) {
break;
} else {
swapValues(index, minimumChildIndex);
}
index = minimumChildIndex;
}
}
/* public void printMinHeap() {
while (size > 0) {
int poll = poll();
System.out.println(poll);
}
}*/
/* public static void main(String[] args) {
MinHeap minHeap = new MinHeap();
minHeap.add(7);
minHeap.add(3);
minHeap.add(4);
minHeap.add(10);
minHeap.add(1);
minHeap.add(15);
minHeap.add(2);
minHeap.add(17);
minHeap.add(1);
minHeap.printMinHeap();
}*/
}