Bug in Heap Sort with Linked List

I'm writing a Heap Sort algorithm for a Linked List in C# and have encountered a bug that I cannot seem to solve. Basically what happens is instead of sorting the list properly, it duplicates some elements and removes others. The result is a list of the same length as original but with missing and duplicated elements and not ordered properly. I have been trying to fix the bug for quite some time but haven't succeeded yet. Could anyone help me spot the problem?

Thanks in advance!

Here's the relevant code:

MyFileList class:

using System;
using System.Collections.Generic;
using System.Text;
using System.IO;

namespace Lab1
{
    class MyFileList : DataList
    {
        int prevNode;
        int currentNode;
        int nextNode;

        public MyFileList(string filename, int n)
        {
            length = n;
            Random rand = new Random();

            if (File.Exists(filename)) File.Delete(filename);

            try
            {
                using (BinaryWriter writer = new BinaryWriter(File.Open(filename,
               FileMode.Create)))
                {
                    writer.Write(4);
                    for (int j = 0; j < length; j++)
                    {
                        char c = (char)rand.Next('a', 'z');
                        int ri = (int)rand.Next();
                        Element e = new Element(c, ri);
                        writer.Write(e.partOne);
                        writer.Write(e.partTwo);
                        writer.Write((j + 1) * 9 + 4); 
                    }
                }
            }
            catch (IOException ex)
            {
                Console.WriteLine(ex.ToString());
            }
        }
        public FileStream fs { get; set; }
        public override Element Head()
        {
            BinaryReader br = new BinaryReader(fs);
            prevNode = -1;
            br.BaseStream.Seek(0, SeekOrigin.Begin); 
            currentNode = br.ReadInt32();
            br.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            char c = (char)br.ReadChar();
            int i = br.ReadInt32();


            Element result = new Element(c, i);
            nextNode = br.ReadInt32();
            return result;
        }
        public override Element Next()
        {
            prevNode = currentNode;
            currentNode = nextNode;
            BinaryReader br = new BinaryReader(fs);
            char c = (char)br.ReadChar(); 
            int i = br.ReadInt32(); 
            Element result = new Element(c, i);
            nextNode = br.ReadInt32(); 
            return result;

        }

        public override Element returnAtIndex(int index)
        {
            //int tempcurrent = currentNode; int tempprev = prevNode; int tempnext = nextNode;

            Element result = Head();
            for (int i = 0; i < index; i++)
            {
                result = Next();
            }

            //Console.WriteLine(prevNode);

            //currentNode = tempcurrent; prevNode = tempprev; nextNode = tempnext;

            return result;
        }

        public override void Swap(int index1, int index2)
        {
            Byte[] data1 = new Byte[6];
            Byte[] data2 = new Byte[6];
            Element e = null;
            BinaryReader br = new BinaryReader(fs);
            BinaryWriter bw = new BinaryWriter(fs);

            Head();
            for (int i = 0; i < index1; i++)
                Next();
            br.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            br.BaseStream.Read(data1, 0, 6);

            Head();
            for (int i = 0; i < index2; i++)
                Next();
            br.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            br.BaseStream.Read(data2, 0, 6);

            Console.WriteLine();


            Head();
            for (int i = 0; i < index1; i++)
                Next();
            bw.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            bw.Write(data2, 0, 6);

            Head();
            for (int i = 0; i < index2; i++)
                Next();
            bw.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            bw.Write(data1, 0, 6);
        }

        public int findNodeofElement(Element e)
        {
            Element elem = Head();
            for (int i = 0; i < length; i++)
            {
                elem = Next();
                if (elem.partOne == e.partOne && elem.partTwo == e.partTwo) break;

            }
            return currentNode;
        }

        public override void setValues(Element e)
        {
            BinaryWriter bw = new BinaryWriter(fs);
            bw.BaseStream.Seek(currentNode, SeekOrigin.Begin);
            bw.Write(e.partOne);
            bw.Write(e.partTwo);
        }

    }

Program.cs:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace Lab1
{
    class Program
    {
        static void Main(string[] args)
        {
            int seed = (int)DateTime.Now.Ticks & 0x0000FFFF;


            rikiavimas(10);

        }


        public static void rikiavimas(int n)
        {
            string filename = @"test1.txt";
            MyFileList myfilelist = new MyFileList(filename, n);
            using (myfilelist.fs = new FileStream(filename, FileMode.Open, FileAccess.ReadWrite))
            {
                Console.WriteLine("\n *****FILE LIST***** \n");
                myfilelist.Print(n);
                PerformHeapSort(myfilelist); 
                Console.WriteLine("\n *****SORTED FILE LIST***** \n");
                myfilelist.Print(n); 
            }
        }

        public static void PerformHeapSort(MyFileList arr)
        {
            int heapSize = arr.Length - 1;
            BuildHeap(arr);
            for (int i = arr.Length - 1; i >= 0; i--) 
            {
               Console.WriteLine("********* " + i);
                if (i!= 0) arr.Swap(0, i);
                heapSize--;
                Heapify(arr, 0);
            } 
        }

        private static void BuildHeap(MyFileList arr)
        {
            int heapSize = arr.Length - 1;
            for (int i = heapSize / 2; i >= 0; i--) 
            {
                Heapify(arr, i);
            }
        }
        private static void Heapify(MyFileList arr, int index)
        {
            int heapSize = arr.Length - 1;
            int left = 2 * index;
            int right = 2 * index + 1;
            int largest = index;

            Element elmLeft = null; Element elmRight = null;
            if (left <= heapSize) elmLeft = arr.returnAtIndex(left);
            if (right <= heapSize) elmRight = arr.returnAtIndex(right);
            Element elmLargest = arr.returnAtIndex(largest);

            if (left <= heapSize && elmLeft > elmLargest) //index
            {
                largest = left;
            }

            if (right <= heapSize && elmRight > elmLargest)
            {
                largest = right;
            }

            if (largest != index)
            {
               if (index != largest) arr.Swap(index, largest);
                Console.WriteLine("*******index is " + index + " largest is " + largest);
                Heapify(arr, largest);
            }
        }



    }

    abstract class DataList
    {
        protected int length;
        public int Length { get { return length; } }
        public abstract Element Head();
        public abstract Element Next();
        //public abstract Element Previous();
        public abstract Element returnAtIndex(int index);
        //public abstract Element returnAtIndex(int index);
        public abstract void Swap(Element a, Element b);
        public abstract void Swap(int index1, int index2);
        public abstract void setValues(Element e);
        //public abstract void Append ()
        //public abstract void PerformHeapSort(DataList list);
        public void Print(int n)
        {

            Element head = Head();
            Console.Write(head.partOne);
            Console.WriteLine(head.partTwo);
            for (int i = 1; i < n; i++)
            {
                Element elem = Next();
                Console.Write(elem.partOne);
                Console.WriteLine(elem.partTwo);
            }
            Console.WriteLine();

        }

    } 

    class Element
    {
        public char partOne;
        public int partTwo;

        public Element (char c, int i)
        {
            partOne = c;
            partTwo = i;
        }

        public void PrintInt()
        {
            Console.WriteLine(partTwo);
        }

        public void PrintChar()
        {
            Console.WriteLine(partOne);
        }

        public static bool operator < (Element e1, Element e2)
        {
            if (e1.partOne < e2.partOne) return true;
            else if (e1.partOne == e2.partOne && (e1.partTwo < e2.partTwo)) return true;
            else return false;
        }

        public static bool operator > (Element e1, Element e2)
        {
            if (e1.partOne > e2.partOne) return true;
            else if (e1.partOne == e2.partOne && (e1.partTwo > e2.partTwo)) return true;
            else return false;
        }
    }
}

Here's an example of the output I get when I run this code:

 *****FILE LIST*****

j849146725
q569436044
r1645801130
p1861344598
k886292186
a852479939
v1166576825
j1180639416
v1227743602
y739268292

 *****SORTED FILE LIST*****

v1227743602
v1227743602
j1180639416
p1861344598
r1645801130
a852479939
y739268292
r1645801130
q569436044
j849146725

I think there may be multiple bugs, but one issue I've found, and I think this is causing the duplicate values, happens when you do a swap.

It appears that the nodes are stored in a binary file in the following format: offset to head node, the node value (a char and an int), and offset to the next node So something like this:

04 00 00 00 67 D0 DB 2C 0E 0D 00 00 00

0x00000004 is the offset to the head node
0x67D0DB2C0E is the head node value (0x67 is the char 'g' and 0x0E2CDBD0 is the int)
0x0000000D is the offset to the next node

I see two approaches to using the linked list: 1) never change the linked-list offsets and just swap the values or 2) leave the values where they are and update the linked-list offsets to swap values. It looks like you're trying to use the first approach in your Print and Next functions. For example in your Next function it simply reads the next node from the file, basically ignoring the linked-list offsets. The problem then comes in your Swap function. It's sort of using a mixture of approach 1 and 2. It uses the offsets from the file but it's also swapping them. The Swap function reads and writes 6 bytes from the file (5 value bytes and the first byte of the offset to the next node). So it's changing the offsets and the values. If you changed it to only read 5 bytes then it would only be changing the values.

You need to make sure all of your code is consistent in how it's using the linked list. Is it going to use the linked-list offsets or is it going to assume that the head node is always at offset 4, and the next node at offset 13?

As I mentioned in the beginning there may be other issues, but I believe this is the one causing the duplicate values.