c++ - Sifting Down From Heap Removal -

i'm trying work heap. i'm inserting few random numbers removing them make sure heap works. problem when i'm removing them duplicate numbers shouldn't exist in heap. pretty i'll insert following numbers , in return: 5 2 10 10 reason.

my main looks this:

#include <iostream> #include <fstream> using namespace std; #include "heap.h"  int main(void) {     heap<int> inlist(4);     inlist.insert(5);     inlist.insert(2);     inlist.insert(3);     inlist.insert(10);     int test;     while(inlist.remove(test))         cout << test << endl; } 

and heap looks this:

#ifndef heap_h #define heap_h  template<typename type> class heap {     private:         type* heapdata;         int currsize;         int capacity;         void _siftup(int);         void _siftdown(int);         int _leftchildof(int) const;         int _parentof(int) const;      public:         heap(int c = 100);         ~heap();         bool viewmax(type&) const;         int getcapacity() const;         int getcurrsize() const;         bool insert(const type&);         bool remove(type&); };  template<typename type> heap<type>::heap(int c = 100) {     capacity = 100;     currsize = 0;     heapdata = new type[capacity]; }  template<typename type> heap<type>::~heap() {     delete[] heapdata;     currsize = 0;     capacity = 0; }  template<typename type> bool heap<type>::insert(const type& datain) {     bool success = false;     if(currsize < capacity)     {         heapdata[currsize] = datain;         _siftup(currsize);         currsize++;         success = true;     }     return success; }  template<typename type> void heap<type>::_siftup(int child) {     type temp;     int parent;     if(child > 0)     {         parent = _parentof(child);         if(heapdata[child] > heapdata[parent])         {             temp = heapdata[parent];             heapdata[parent] = heapdata[child];             heapdata[child] = temp;             _siftup(child);         }     } }  template<typename type> bool heap<type>::remove(type& dataout) {     bool success = false;     if(currsize > 0)     {         dataout = heapdata[0];         currsize--;         heapdata[0] = heapdata[currsize];         _siftdown(0);         success =  true;     }     return success; }  template<typename type> void heap<type>::_siftdown(int parent) {     type temp;     int child = _leftchildof(parent);     if(child < currsize)     {         if((child + 1 < currsize) && (heapdata[child] < heapdata[child + 1]))             child++;          if(child)         {             temp = heapdata[child];             heapdata[child] = heapdata[child + 1];             heapdata[child + 1] = temp;             _siftdown(child);         }     } }  template<typename type> int heap<type>::_leftchildof(int p) const {     return(2 * p + 1); }  template<typename type> int heap<type>::_parentof(int c) const {     return((c - 1) / 2); } //************************************************************************** template<typename type> int heap<type>::getcapacity() const {     return capacity; }  template<typename type> int heap<type>::getcurrsize() const {     return currsize; }  template<typename type> bool heap<type>::viewmax(type& max) const {     return false; } #endif 

i'm pretty sure problem isn't when i'm inserting heap when i'm removing it.

edit changed _siftdown bit - numbers show 5 10 3 2

if(child) {     temp = heapdata[child];     heapdata[child] = heapdata[parent];     heapdata[parent] = temp;     _siftdown(child); } 

your _siftdown broken,

template<typename type> void heap<type>::_siftdown(int parent) {     type temp;     int child = _leftchildof(parent);     if(child < currsize)     {         if((child + 1 < currsize) && (heapdata[child] < heapdata[child + 1]))             child++;          if(child) 

what's meant check? child @ point either 2*parent + 1 or 2*parent + 2, without overflow, since parent should >= 0, positive ~> condition fulfilled.

you need check whether want swap heapdata[parent] , heapdata[child], condition should if (heapdata[parent] < heapdata[child]).

        {             temp = heapdata[child];             heapdata[child] = heapdata[child + 1];             heapdata[child + 1] = temp; 

you swapping elements @ index child , child+1, that's wrong. should swap heapdata[child] , heapdata[parent] here.

            _siftdown(child);         }     } } 

you have error in _siftup,

template<typename type> void heap<type>::_siftup(int child) {     type temp;     int parent;     if(child > 0)     {         parent = _parentof(child);         if(heapdata[child] > heapdata[parent])         {             temp = heapdata[parent];             heapdata[parent] = heapdata[child];             heapdata[child] = temp;             _siftup(child);         }     } } 

the recursive call should _siftup(parent), otherwise never sift item more 1 level.