# Heap (Looking for crits)

This topic is 2953 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I've been programming awhile and am in a Computer Science program. Gone to several competitions (won CCSC at Franklin college this year).

Basically looking for crits / potential speed ups in my heap. Got bored, never implemented one so decided to do it today.

main (test case with time)
#include <iostream>#include <ctime>#include <Windows.h>#include "Heap.h"using namespace std;int main(){	Heap<int> mine;	srand(time(NULL));	time_t begin, end;	begin = GetTickCount();	for(unsigned int i = 0; i < 100000; i++)	{		mine.push(rand());	}	end = GetTickCount();	cout << end - begin << endl;	for(unsigned int i = 0; i < 100000; i++)	{		mine.pop();	}	end = GetTickCount();	cout << end - begin << endl;	return 0;}

Heap.h
#pragma once#include <iostream>#include <algorithm>#include <vector>using namespace std;template<typename H>class Heap{	static bool comp(const H& a, const H& b)	{		return a > b;	}	inline void filterUp()	{		//a nodes parent is (n-1)/2 and since n is SIZE -1, substitute		//and get (SIZE-2)/2		unsigned int n(SIZE -1), nPar( (SIZE-2)/2);		H temp;		while(n > 0 && Heap<H>::comp(nodes[n], nodes[nPar]) )		{			temp = nodes[nPar];			nodes[nPar] = nodes[n];			nodes[n] = temp;			n = nPar;			nPar = (n - 1) /2;		}	}//filter	inline void filterDown()	{		if(SIZE <= 1)			return;		//initialize when created (saves a copy)		unsigned int n(0), nChi1(1), nChi2(2), toSwap;		H temp;		while(nChi1 < SIZE)		{			if(nChi2 < SIZE)			{				//if compare function returns true than use nChi1 as index				toSwap = comp(nodes[nChi1], nodes[nChi2]) ? nChi1 : nChi2;				if(comp(nodes[toSwap], nodes[n]))				{					//temp variable					temp = nodes[toSwap];					nodes[toSwap] = nodes[n];					nodes[n] = temp;					n = toSwap;					//New child index					nChi1 = n*2+1;					nChi2 = n*2+2;				}//if statement				else					break;			}//if child 2 is big enough			else			{				//now if there is no 2nd child to current parent				//check compare, if true swap				if(comp(nodes[nChi1], nodes[n]))				{					temp = nodes[nChi1];					nodes[toSwap] = nodes[n];					nodes[n] = temp;					break;				}//if statement				break;			}		}	}	unsigned int SIZE;	vector<H> nodes;public:	Heap(unsigned int Reserve = 30);	Heap(const H& Data, unsigned int Reserve = 30);	Heap(H Data, unsigned int Reserve = 30);	Heap(const vector<H>& Data);	void push(H& Data);	void push(H Data);	void pop();	const H& front()	{		if(SIZE > 0)			return nodes[0];	}	~Heap(void);};#include "Heap.inl"

Heap.inl (because vs 2008 doesn't have export working it seems so just tossed it in another file without .cpp)
#pragma once#include "Heap.h"template<typename H>inline Heap<H>::Heap(unsigned int Reserve) : SIZE(0){	nodes.reserve(Reserve);}template<typename H>inline Heap<H>::Heap(const H& Data, unsigned int Reserve) : SIZE(1){	nodes.reserve(Reserve);	nodes.push_back(Data);}template<typename H>inline Heap<H>::Heap(H Data, unsigned int Reserve) : SIZE(1){	nodes.reserve(Reserve);	nodes.push_back(Data);}template<typename H>inline Heap<H>::Heap(const vector<H>& Data){	//Copy the vector in and sort it (sorted high to low will give a heap)	SIZE = Data.size();	nodes.reserve(SIZE*2);	//copy Data into nodes	copy(Data.begin(), Data.end(), nodes.begin());	//Sort to create a heap	sort(nodes.begin(), nodes.end, heap::comp);}template<typename H>inline Heap<H>::~Heap(void){}template<typename H>void inline Heap<H>::push(H& Data){	SIZE++;	nodes.push_back(Data);	filterUp();}template<typename H>void inline Heap<H>::push(H Data){	SIZE++;	nodes.push_back(Data);	filterUp();}template<typename H>void inline Heap<H>::pop(){	//swap the front with the back	swap((*nodes.begin()), (*(nodes.end()-1)));	nodes.pop_back();	SIZE --;	filterDown();}

Also I understand sorting isn't the best way to create a heap from a vector, but that wasn't my main priority. Main priority was to get push and pop working quickly.

From AMD's Profiler
CS:EIP Symbol + Offset 64-bit Timer samples
0x11414c0 Heap<int>::filterDown 85.71
0x11413d0 Heap<int>::filterUp 7.14
0x1141110 main 3.57
0x11412b0 Heap<int>::pop 3.57

4 functions, 20 instructions, Total: 28 samples, 100.00% of shown samples, 2.79% of total session samples
16 ms for all the pushes to happen
47 for everything to happen.

##### Share on other sites
Interesting, but off hand I see a few critical flaws. They are flaws in what you are doing, not flaws in the code itself, which I'll let others point out.

Premature optimization. The chunk of code is simply not going to be a bottleneck in the real world. Granted, you wouldn't want to introduce pessimizations to it, but even a simple implementation should have excellent real-world performance. It is an optimization of the wrong thing. The correct optimization would be at other levels of the program.

Invalid profile results. This goes along closely with the previous one. Your normal use case is going to be a tight loop that fits in the CPU cache and the compiler can trivially optimize. To get a realistic view of performance you need to do some serious work with it.

Duplicated functionality. This is re-inventing the wheel. Instead of offering an improvement, the code will have TWO versions instead of just one. Given the choice between the standard library and a hacked-together template, I'd pick the standard library. Look at the C++ language's push_heap(), pop_heap(), make_heap(), and sort_heap() functions. It also looks like you may have a few more comparisons than the maximums guaranteed by the standard.

Other less-critical flaws are that your code has more exceptional behavior (="more likely to generate exceptions") than the built in versions, such as creating and assigning to temporaries rather than std::swap(). It is generally a flaw to combine two jobs of memory/container management and data structure management; if you wanted a sorted container then pick an associative container that does the right thing by default.

##### Share on other sites
Don't use inline, templates are inline expanded anyway.

std::vector is used, yet unsigned int is used for iteration. Elements in vector are indexed by vector<T>::size_type, which may be larger than int.

Quote:
 temp = nodes[nPar]; nodes[nPar] = nodes[n]; nodes[n] = temp;
See std::swap.

Quote:
 static bool comp(const H& a, const H& b)
Make this a free function.

Quote:
 inline void filterUp() { //a nodes parent is (n-1)/2 and since n is SIZE -1, substitute //and get (SIZE-2)/2 unsigned int n(SIZE -1), nPar( (SIZE-2)/2);
Considering SIZE is unsigned, what happens if SIZE is 1? Also, ALLCAPSNAMES are usually reserved for macros or constants.

Quote:
 const H& front() { if(SIZE > 0) return nodes[0]; }
This shouldn't even compile since it doesn't always return.

Quote:
 using namespace std;
Don't put this into global scope, definitely not into headers, maybe into cpp. Inside function body it's ok.

Quote:
 nChi1 = n*2+1;nChi2 = n*2+2;
I didn't go through code, but indexing is usually zero-based, so children are 2n and 2n+1. Maybe this is something else though.

Put these to on top of main cpp file:
Quote:
 #define _HAS_ITERATOR_DEBUGGING 0#define _SECURE_SCL 0
Then run the benchmarks again.

##### Share on other sites
About the front yeah I was thinking that before, then got side tracked and never went back to it. The premature optimization isn't for anything. It is more of to get insight on what I am doing one way, and should be done a different way. Will fix those items and rerun benchmarks when I can.

Frob, I am not using this for anything, just doing it as an exercise since I've never programmed a heap (I like to implement things to understand them better, although a heap is relatively easy it was just for a quick exercise).

Thanks for the replies.

1. 1
Rutin
54
2. 2
3. 3
4. 4
5. 5

• 10
• 28
• 20
• 9
• 20
• ### Forum Statistics

• Total Topics
633412
• Total Posts
3011732
• ### Who's Online (See full list)

There are no registered users currently online

×