Double free or corruption C++

I'm getting an odd error which occurs even though I am calling free(), the use is in a method called dequeue which removes elements from a priority queue, the functionality works fine but when the queue is empty the error is thrown instead of the error message which is defined.

Code and Error below:

int dequeue()
        {try{
            PRecord *tmp; //pointer to front of queue

            if(front!=NULL){
                tmp = front;
                cout<<"Deleted item is: "<<endl;
                displayRecord(tmp); //outputs record details
                front = front->link; //link to the front

                free(tmp); //dealloc memory no longer used


            }
            else{
            cerr<<"Queue is empty - No items to dequeue!"<<endl;    
                }
        } catch(...){
            return(0);
        }

            }





*** glibc detected *** ./3x: double free or corruption (fasttop): 0x0000000000bb3040 ***
======= Backtrace: =========
/lib64/libc.so.6[0x35a8675dee]
/lib64/libc.so.6[0x35a8678c3d]
./3x[0x401275]
./3x[0x400f69]
/lib64/libc.so.6(__libc_start_main+0xfd)[0x35a861ed1d]
./3x[0x400d59]
======= Memory map: ========
00400000-00402000 r-xp 00000000 08:06 2623369                            /home/std/rc14lw/lab5excercisefinal/3x
00601000-00602000 rw-p 00001000 08:06 2623369                            /home/std/rc14lw/lab5excercisefinal/3x
00bb3000-00bd4000 rw-p 00000000 00:00 0                                  [heap]
35a8200000-35a8220000 r-xp 00000000 08:01 1310722                        /lib64/ld-2.12.so
35a8420000-35a8421000 r--p 00020000 08:01 1310722                        /lib64/ld-2.12.so
35a8421000-35a8422000 rw-p 00021000 08:01 1310722                        /lib64/ld-2.12.so
35a8422000-35a8423000 rw-p 00000000 00:00 0
35a8600000-35a878a000 r-xp 00000000 08:01 1310723                        /lib64/libc-2.12.so
35a878a000-35a898a000 ---p 0018a000 08:01 1310723                        /lib64/libc-2.12.so
35a898a000-35a898e000 r--p 0018a000 08:01 1310723                        /lib64/libc-2.12.so
35a898e000-35a8990000 rw-p 0018e000 08:01 1310723                        /lib64/libc-2.12.so
35a8990000-35a8994000 rw-p 00000000 00:00 0
35a8a00000-35a8a83000 r-xp 00000000 08:01 1310764                        /lib64/libm-2.12.so
35a8a83000-35a8c82000 ---p 00083000 08:01 1310764                        /lib64/libm-2.12.so
35a8c82000-35a8c83000 r--p 00082000 08:01 1310764                        /lib64/libm-2.12.so
35a8c83000-35a8c84000 rw-p 00083000 08:01 1310764                        /lib64/libm-2.12.so
7fe714000000-7fe714021000 rw-p 00000000 00:00 0
7fe714021000-7fe718000000 ---p 00000000 00:00 0
7fe71a6f6000-7fe71a6f9000 rw-p 00000000 00:00 0
7fe71a6f9000-7fe71a70e000 r-xp 00000000 08:01 3809328                    /usr/local/gnat/lib64/libgcc_s.so.1
7fe71a70e000-7fe71a90d000 ---p 00015000 08:01 3809328                    /usr/local/gnat/lib64/libgcc_s.so.1
7fe71a90d000-7fe71a90e000 rw-p 00014000 08:01 3809328                    /usr/local/gnat/lib64/libgcc_s.so.1
7fe71a90e000-7fe71a90f000 rw-p 00000000 00:00 0
7fe71a924000-7fe71a927000 rw-p 00000000 00:00 0
7fe71a927000-7fe71aa09000 r-xp 00000000 08:01 3823893                    /usr/local/gnat/lib64/libstdc++.so.6.0.17
7fe71aa09000-7fe71ac08000 ---p 000e2000 08:01 3823893                    /usr/local/gnat/lib64/libstdc++.so.6.0.17
7fe71ac08000-7fe71ac10000 r--p 000e1000 08:01 3823893                    /usr/local/gnat/lib64/libstdc++.so.6.0.17
7fe71ac10000-7fe71ac12000 rw-p 000e9000 08:01 3823893                    /usr/local/gnat/lib64/libstdc++.so.6.0.17
7fe71ac12000-7fe71ac28000 rw-p 00000000 00:00 0
7ffd0b122000-7ffd0b137000 rw-p 00000000 00:00 0                          [stack]
7ffd0b1a1000-7ffd0b1a2000 r-xp 00000000 00:00 0                          [vdso]
ffffffffff600000-ffffffffff601000 r-xp 00000000 00:00 0                  [vsyscall]