(转)Heap 数据结构

Heap 有大小分,此处的小堆转自:

https://www.codeproject.com/tips/816934/min-binary-heap-implementation-in-cplusplus

MinHeap.hxx:

#include <vector>

namespace MinHeapNS
{

using std::vector;

class MinHeap {
private:
  vector<int> _vector;
  void BubbleDown(int index);
  void BubbleUp(int index);
  void Heapify();

public:
  MinHeap(int* array, int length);
  MinHeap(const vector<int>& vector);
  MinHeap();

  void Insert(int newValue);
  int GetMin();
  void DeleteMin();
};
} // MinHeapNS

MinHeap.cxx

#include "MinHeap.hxx"

using MinHeapNS::MinHeap;

MinHeap::MinHeap(int* array, int length) : _vector(length)
{
  for(int i = 0; i < length; ++i) {
    _vector[i] = array[i];
  }

  Heapify();
}

MinHeap::MinHeap(const vector<int>& vector) : _vector(vector) {
  Heapify();
}

MinHeap::MinHeap() { }

void MinHeap::Heapify() {
  int length = _vector.size();
  for(int i=length-1; i>=0; --i) {
    BubbleDown(i);
  }
}

void MinHeap::BubbleDown(int index) {
  int length = _vector.size();
  int leftChildIndex = 2*index + 1;
  int rightChildIndex = 2*index + 2;

  if(leftChildIndex >= length)
    return; //index is a leaf

  int minIndex = index;

  if(_vector[index] > _vector[leftChildIndex]) {
    minIndex = leftChildIndex;
  }
  
  if((rightChildIndex < length) && (_vector[minIndex] > _vector[rightChildIndex])) {
    minIndex = rightChildIndex;
  }

  if(minIndex != index) {
    //need to swap
    int temp = _vector[index];
    _vector[index] = _vector[minIndex];
    _vector[minIndex] = temp;
    BubbleDown(minIndex);
  }
}

void MinHeap::BubbleUp(int index) {
  if(index == 0)
    return;

  int parentIndex = (index-1)/2;

  if(_vector[parentIndex] > _vector[index]) {
    int temp = _vector[parentIndex];
    _vector[parentIndex] = _vector[index];
    _vector[index] = temp;
    BubbleUp(parentIndex);
  }
}

void MinHeap::Insert(int newValue) {
  int length = _vector.size();
  _vector[length] = newValue;

  BubbleUp(length);
}

int MinHeap::GetMin() {
  return _vector[0];
}
  
void MinHeap::DeleteMin() {
  int length = _vector.size();

  if(length == 0) {
    return;
  }
  
  _vector[0] = _vector[length-1];
  _vector.pop_back();

  BubbleDown(0);
}

main:

// https://www.codeproject.com/tips/816934/min-binary-heap-implementation-in-cplusplus

#include "MinHeap.hxx"
#include <iostream>

using MinHeapNS::MinHeap;
using std::cout;
using std::cin;

int main(int argc, char const* argv[]) {
  int array[] = {10, 4, 5, 30, 3, 300};

  MinHeap minHeap(array, 6);

  for(int i=0; i<3; ++i) {
    cout << minHeap.GetMin() << "  ";
    minHeap.DeleteMin();
  }

  char x;
  cin >> x;

  return 0;
}

转载自:

  1. https://www.codeproject.com/tips/816934/min-binary-heap-implementation-in-cplusplus

作者: YanWen

Web 开发者

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s