kopia lustrzana https://github.com/jameshball/osci-render
41 wiersze
1012 B
C++
41 wiersze
1012 B
C++
#pragma once
|
|
|
|
#include "Globals.h"
|
|
#include <vector>
|
|
using namespace std;
|
|
|
|
/*
|
|
This is a binary heap for pairs of the type (double key, int satellite)
|
|
It is assumed that satellites are unique integers
|
|
This is the case with graph algorithms, in which satellites are vertex or edge indices
|
|
*/
|
|
class BinaryHeap
|
|
{
|
|
public:
|
|
BinaryHeap(): satellite(1), size(0) {};
|
|
|
|
//Inserts (key k, satellite s) in the heap
|
|
void Insert(double k, int s);
|
|
//Deletes the element with minimum key and returns its satellite information
|
|
int DeleteMin();
|
|
//Changes the key of the element with satellite s
|
|
void ChangeKey(double k, int s);
|
|
//Removes the element with satellite s
|
|
void Remove(int s);
|
|
//Returns the number of elements in the heap
|
|
int Size();
|
|
//Resets the structure
|
|
void Clear();
|
|
|
|
private:
|
|
vector<double> key;//Given the satellite, this is its key
|
|
vector<int> pos;//Given the satellite, this is its position in the heap
|
|
vector<int> satellite;//This is the heap!
|
|
|
|
//Number of elements in the heap
|
|
int size;
|
|
};
|
|
|
|
|
|
|