1using System;
2using System.Collections.Generic;
3using System.Text;
4
5namespace Heap
6{
7    class Program
8    {
9        static void Main(string[] args)
10        {
11            int len = 100;
12            Heap heap = new Heap();
13
14            Random random = new Random();
15
16            for (int i = 0; i < len; i++)
17            {
18                int data = random.Next(1, 100000);
19                heap.Insert(data);
20            }
21
22            for (int i = 0; i < len; i++)
23            {
24                int data = heap.Delete();
25                System.Console.WriteLine(data);
26            }
27
28            System.Console.WriteLine("ok");
29        }
30    }
31
32    class Heap
33    {
34        private List<int> _nodes;
35
36        public Heap()
37        {
38            _nodes = new List<int>();
39        }
40
41        public void Insert(int data)
42        {
43            _nodes.Add(data);
44
45            chechUp(_nodes.Count - 1);
46        }
47
48        private void chechUp(int downIndex)
49        {
50            int parentIndex;
51
52            while ( (parentIndex = getParentIndex(downIndex)) != -1)
53            {
54                if (_nodes[downIndex] > _nodes[parentIndex])
55                {
56                    int data = _nodes[downIndex];
57                    _nodes[downIndex] = _nodes[parentIndex];
58                    _nodes[parentIndex] = data;
59
60                    downIndex = parentIndex;
61                }
62                else
63                {
64                    break;
65                }
66            }
67        }
68
69        public int Delete()
70        {
71            if (_nodes.Count == 0)
72            {
73                throw new Exception("no more element to delete.");
74            }
75
76            int data = _nodes[0];
77
78            _nodes[0] = _nodes[_nodes.Count - 1];
79
80            _nodes.RemoveAt(_nodes.Count - 1);
81
82            chechDown(0);
83
84            return data;
85        }
86
87        private void chechDown(int upIndex)
88        {
89            int lChildIndex;
90            int rChildIndex;
91            int downIndex;
92
93            lChildIndex = getLChildIndex(upIndex);
94            rChildIndex = getRChildIndex(upIndex);
95
96            while (lChildIndex != -1)
97            {
98                //只考虑父节点和左子树的关系
 99                if (rChildIndex == -1)
100                {
101                    downIndex = lChildIndex;
102                }
103                else
104                {
105                    downIndex = _nodes[lChildIndex] > _nodes[rChildIndex] ? lChildIndex : rChildIndex;
106                }
107
108                if (_nodes[upIndex] < _nodes[downIndex])
109                {
110                    int data = _nodes[downIndex];
111                    _nodes[downIndex] = _nodes[upIndex];
112                    _nodes[upIndex] = data;
113
114                    upIndex = downIndex;
115
116                    lChildIndex = getLChildIndex(upIndex);
117                    rChildIndex = getRChildIndex(upIndex);
118                }
119                else
120                {
121                    break;
122                }
123
124            }
125
126
127        }
128
129        private int getLChildIndex(int parentIndex)
130        {
131            int lChildIndex = parentIndex * 2;
132
133            lChildIndex += 1;
134
135            return lChildIndex <= _nodes.Count - 1 ? lChildIndex : -1;
136        }
137
138        private int getRChildIndex(int parentIndex)
139        {
140            int rChildIndex = parentIndex * 2;
141
142            rChildIndex += 2;
143
144            return rChildIndex <= _nodes.Count - 1 ? rChildIndex : -1;
145        }
146
147        /**//// <summary>
148        /// 如果该节点是跟节点，则无法给出其父节点，故以-1代替。
149        /// </summary>
150        /// <param name="childIndex"></param>
151        /// <returns></returns>
152        private int getParentIndex(int childIndex)
153        {
154            // 如果该节点是跟节点，则无法给出其父节点，故以-1代替。
155            if (childIndex == 0)
156            {
157                return -1;
158            }
159
160            childIndex++;
161
162            //向下取整
163            return (int)(childIndex / 2) - 1;
164        }
165    }
166
167    class HeapNode
168    {
169        public int _data;
170        public HeapNode _parent;
171        public HeapNode _lChild;
172        public HeapNode _rChild;
173
174        public HeapNode(int data)
175        {
176            _data = data;
177            _parent = null;
178            _lChild = null;
179            _rChild = null;
180        }
181    }
182
183}
184