데이터 구조 이 진 더미 C + + 최소 더미 구현
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
template<class Comparable>
class BinaryHeap
{
public:
BinaryHeap();
explicit BinaryHeap(const vector<Comparable>& items);
bool isEmpty() const;
const Comparable& findMin() const;
void insert(const Comparable& x);
void deleteMin();
void deleteMin(Comparable& minItem);
void makeEmpty();
void printHeap() const;
private:
int currentSize;
vector<Comparable> array;
void buildheap();
void percolateDown(int hole);
};
template<class Comparable>
BinaryHeap<Comparable>::BinaryHeap() : currentSize(0)
{
array.push_back(Comparable());
}
template<class Comparable>
BinaryHeap<Comparable>::BinaryHeap(const vector<Comparable>& items) : array(items.size() + 1), currentSize(items.size())
{
for(size_t i = 0; i < items.size(); ++i)
array[i + 1] = items[i];
buildheap();
}
template<class Comparable>
bool BinaryHeap<Comparable>::isEmpty() const
{
return currentSize == 0;
}
template<class Comparable>
const Comparable& BinaryHeap<Comparable>::findMin() const
{
return array[1];
}
template<class Comparable>
void BinaryHeap<Comparable>::insert(const Comparable& x)
{
int hole = ++currentSize;
array.push_back(x);
for(;hole > 1 && x < array[hole / 2]; hole /= 2)
array[hole] = array[hole / 2];
array[hole] = x;
}
template<class Comparable>
void BinaryHeap<Comparable>::deleteMin()
{
if(isEmpty())
return;
array[1] = array[currentSize--];
percolateDown(1);
}
template<class Comparable>
void BinaryHeap<Comparable>::deleteMin(Comparable &minItem)
{
if(isEmpty())
return;
minItem = array[1];
array[1] = array[currentSize--];
percolateDown(1);
}
template<class Comparable>
void BinaryHeap<Comparable>::makeEmpty()
{
array.clear();
currentSize = 0;
array.push_back(Comparable());
}
template<class Comparable>
void BinaryHeap<Comparable>::buildheap()
{
for(int i = currentSize / 2; i > 0; --i)
percolateDown(i);
}
template<class Comparable>
void BinaryHeap<Comparable>::percolateDown(int hole)
{
int child;
Comparable tmp = array[hole];
for(; hole * 2 <= currentSize; hole = child)
{
child = hole * 2;
if(child != currentSize && array[child + 1] < array[child])
++child;
if(array[child] < tmp)
array[hole] = array[child];
else
break;
}
array[hole] = tmp;
}
template<class Comparable>
void BinaryHeap<Comparable>::printHeap() const
{
copy(array.begin() + 1, array.begin() + currentSize + 1, ostream_iterator<Comparable>(cout, " "));
}
int main()
{
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.