首页 > 代码库 > C# 堆

C# 堆

2024-07-22 19:57:59   210人阅读

C# 堆
堆是一种非常有用的数据结构，下面的C#以插入数据的方式创建最大堆，然后实现了堆的插入和删除操作。
  //构建最大堆,
    public class MyHeap
    {
        List<int> heap = new List<int>();
        int temp;
        public MyHeap()
        {
            heap.Insert(0, -1);//第0位置保存数据-1，该数据无用
        }
        public void insertData(int d)
        {
            heap.Insert(heap.Count, d);
            adjustUp(heap.Count-1);
        }
        //向上调整堆
        private void adjustUp(int position)
        {
            //当前点的父节点数据小于当前点,则需要交换当前点父节点，接下来需要递归对当前点的父节点进行操作
            if (Math.Floor((double)position / 2) > 0 && heap[(int)(Math.Floor((double)position / 2))] < heap[position])
            {
                exchange(position, (int)(Math.Floor((double)position / 2)));
                adjustUp((int)(Math.Floor((double)position / 2)));
            }
        }
        //向下调整堆
        private void adjustDown(int position)
        {
            if (position * 2 < heap.Count && heap[position] < heap[position * 2])
            {
                exchange(position, position * 2);
                adjustDown(position * 2);
            }
            else if (position * 2+1 < heap.Count && heap[position] < heap[position * 2+1])
            {
                exchange(position, position * 2+1);
                adjustDown(position * 2+1);
            }
        }
        private void exchange(int i,int j)
        {
            temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }
        //遍历找到第一个数值=d的节点i，将堆的最后一个节点挪到i处，向下递归调整i为根节点的堆
        public void deleteData(int d)
        {
            int i =0;
            for ( i = 1; i < heap.Count; i++)
            {
                if (heap[i] == d)
                    break;
            }
            if (i == heap.Count)
                return;
            else
            {
                heap[i] = heap[heap.Count - 1];
                heap.RemoveAt(heap.Count - 1);
                adjustDown(i);
            }
        }
        public void printHeap()
        {
            for (int i = 1; i < heap.Count; i++)
            {
                Console.Write(heap[i] + " ");
            }
        }
    }
下面是测试的程序：插入数据构建堆，然后删除数据。
  MyHeap myheap = new MyHeap();
            myheap.printHeap();
            myheap.insertData(45);
            myheap.insertData(36);
            myheap.insertData(18);
            myheap.insertData(53);
            myheap.insertData(72);
            myheap.insertData(30);
            myheap.insertData(48);
            myheap.insertData(93);
            myheap.insertData(15);
            myheap.insertData(35);
            myheap.printHeap();
            Console.WriteLine("");
            Console.WriteLine("删除72");
            myheap.deleteData(72);
            myheap.printHeap();
            Console.Read();


C# 堆


联系
我们