数据的逻辑结构：数据对象中数据元素之间的相互关系；
数据的物理结构：数据的逻辑结构在计算机中的储存方式。
物理结构（储存结构）包括顺序储存结构和链式储存结构。
顺序储存结构：把数据储存到相邻的储存单元中；
链式储存结构：数据元素任意的储存到储存单元中，每个元素用一个指针指向下一个数据元素，将它们联系起来。
在一个集合中，如果一个数出现的频率超过50%，那么称这个数为该集合的主元素。
规则技巧：去除集合中两个不相等的数，其主元素出现的频率仍然大于50%。
使用两个变量，count=0和size=集合大小，假设第一个元素为主元素，依次和后面的数对比，相同count就+1，不相同count就-1，当count=-1时就代表前面的所有值都刚好是成对不相同的值，则可以抛弃掉。则设count=0,继续假设下一个元素m为主元素，继续跟后面元素比较。一直到count>=(size-m)/2，假设的主元素为真主元素。
树的一种应用，例如查询两个点是否联通，可以将相连的点点们构造成一棵二叉树，这样，一颗二叉树就是表示一个集合一个联通，这样就是一个并集。当你要查询两个点是否联通的时候，只需要查询这两个点是否有同样的来源（树的根节点）。
Prim算法是针对点来求最小生成树的，取一个起点添加到左集合中，右集合中有除左集合的点的其他点。左集合链接右集合，取使边权重最小的右集合的点加入到左集合中，链接这两个点。继续去左集合链接右集合权重最小的边的点，循环到所有的点都链接起来。
最小生成树就是一个无序的图，求出联通所有点的树，使得他们链接的边的累计权重最小。
Kruskal算法是一个对边进行操作的算法，将所有边放到一个集合当中，根据权重由小到大排列，依次取出，并判断这条边是否可以连接（边的两点是否已经联通，可以用并查集检测），如果没有就链接起来，如果有就舍弃这条边，直到所有的点都连接了起来。
//最小堆（二叉树的一种）
class Dui
{
public int[] datas;
public Dui(int maxLength) {
if (maxLength <= 0)
{
datas = new int[16 + 1];
}
else {
datas = new int[maxLength + 1];
}
}
public void CompareAndReplace(int data) {
if (data > datas[1]) {
datas[1] = data;
SiftDown(1);
}
}
//向下调整
public void SiftDown(int index) {
bool isNeedSwap = true;
int t = index;
//有左儿子
while (index * 2 <= datas[0] && isNeedSwap) {
if (datas[index] > datas[index * 2]) {
t = index * 2;
}
//有右儿子
if (index * 2 + 1 <= datas[0]) {
if (datas[t] > datas[index * 2 + 1]) {
t = index * 2 + 1;
}
}
if (index != t)
{
int temp = datas[index];
datas[index] = datas[t];
datas[t] = temp;
index = t;
}
else {
//比左右两儿子都小了
isNeedSwap = false;
}
}
}
public void Insert(int val) {
if (datas.Length - 1 == datas[0]) {
//我这里就不重构数组了
Console.WriteLine("最小堆已满!");
return;
}
int insertIndex = datas[0] + 1;
datas[insertIndex] = val;
datas[0]++;
SiftUp(insertIndex);
}
public override string ToString() {
string ss = "";
for (int i = 1; i <= datas[0]; i++) {
ss += i+":" + datas[i] + " ";
}
return ss;
}
}
static void Main(string[] args)
{
Dui dui = new Dui(3);
int[] datas = { 10, 5, 3, 99, 1, 5, 6, 20, 7, 33 };
dui.Insert(datas[0]);
dui.Insert(datas[1]);
dui.Insert(datas[2]);
for (int i = 3; i < datas.Length; i++) {
dui.CompareAndReplace(datas[i]);
}
Console.WriteLine(dui);
Console.ReadKey();
}利用最小堆根节点的元素为堆中的最小值，先生成一个只有3个元素的堆（假如找前三大的），随机初始化，然后一一比较要寻找的数据和根节点，只要比根节点小的，都不是第三大的数值，如果比根节点数据大，这才舍弃根节点数据替换为当前比较数值，再向下调整，继续比较。
//最小堆
class Dui
{
public int[] datas;
public Dui(int maxLength) {
if (maxLength <= 0)
{
datas = new int[16 + 1];
}
else {
datas = new int[maxLength + 1];
}
}
public int Pop() {
int temp = datas[1];
datas[1] = datas[datas[0]];
datas[0]--;
SiftDown(1);
return temp;
}
public bool isEmpty() {
return datas[0] == 0 ? true:false;
}
public void ValueTo(int[] copyValues) {
datas[0] = copyValues.Length;
if (datas[0] < 1) {
return;
}
for (int i = 1; i <= datas[0]; i++) {
datas[i] = copyValues[i-1];
}
Create();//调整节点
}
public void Create() {
//倒数最后一个非叶节点
int index = datas[0] / 2;
for (int i = index; i >= 1; i--) {
SiftDown(i);
}
}
//向下调整
public void SiftDown(int index) {
bool isNeedSwap = true;
int t = index;
//有左儿子
while (index * 2 <= datas[0] && isNeedSwap) {
if (datas[index] > datas[index * 2]) {
t = index * 2;
}
//有右儿子
if (index * 2 + 1 <= datas[0]) {
if (datas[t] > datas[index * 2 + 1]) {
t = index * 2 + 1;
}
}
if (index != t)
{
int temp = datas[index];
datas[index] = datas[t];
datas[t] = temp;
index = t;
}
else {
//比左右两儿子都小了
isNeedSwap = false;
}
}
}
}
static void Main(string[] args)
{
int[] datas = new int[100000];
Random random = new Random();
for (int i = 0; i < 100000; i++) {
datas[i] = random.Next(1, 10000);
}
Stopwatch stopwatch = new Stopwatch();
Dui dui = new Dui(100000);
dui.ValueTo(datas);
stopwatch.Start();
int j = 0;
while (!dui.isEmpty()) {
datas[j++] = dui.Pop();
}
stopwatch.Stop();
for (j = 0; j < 100000; j++) {
Console.WriteLine(datas[j]);
}
Console.WriteLine("用时：" + stopwatch.ElapsedMilliseconds);
Console.ReadKey();
}堆排序，就是利用最小堆，每次都能确定根节点的值就是当前集合中的最小值，所以每次只要将根节点输出，然后将最后一个节点替换上来再向下调整，形成新的最小堆。输出完毕，就是排序完毕了。
还有一种思路就是利用最大堆，根节点为当前集合的最大值，与最后一个节点交换，树长度减1.再向下调整，形成新的最大堆，再和最后一个元素交换....到最后树的长度只有1时，你把树的长度恢复，你会发现这是一个工整的最小堆，按数组顺序输出就是排序好的了。
模拟排序10W条随机数据用时：58ms
//最小堆
class Dui
{
public int[] datas;
public Dui() {
datas = new int[16 + 1];
}
public Dui(int maxLength) {
if (maxLength <= 0)
{
datas = new int[16 + 1];
}
else {
datas = new int[maxLength + 1];
}
}
public void ValueTo(int[] copyValues) {
datas[0] = copyValues.Length;
if (datas[0] < 1) {
return;
}
for (int i = 1; i <= datas[0]; i++) {
datas[i] = copyValues[i-1];
}
Create();//调整节点
}
public void Create() {
//倒数最后一个非叶节点
int index = datas[0] / 2;
for (int i = index; i >= 1; i--) {
SiftDown(i);
}
}
//向下调整
public void SiftDown(int index) {
bool isNeedSwap = true;
int t = index;
//有左儿子
while (index * 2 <= datas[0] && isNeedSwap) {
if (datas[index] > datas[index * 2]) {
t = index * 2;
}
//有右儿子
if (index * 2 + 1 <= datas[0]) {
if (datas[t] > datas[index * 2 + 1]) {
t = index * 2 + 1;
}
}
if (index != t)
{
int temp = datas[index];
datas[index] = datas[t];
datas[t] = temp;
index = t;
}
else {
//比左右两儿子都小了
isNeedSwap = false;
}
}
}
public void Insert(int val) {
if (datas.Length - 1 == datas[0]) {
//我这里就不重构数组了
Console.WriteLine("最小堆已满!");
return;
}
int insertIndex = datas[0] + 1;
datas[insertIndex] = val;
datas[0]++;
SiftUp(insertIndex);
}
//向上调整
public void SiftUp(int index) {
if (index == 1) return;
bool isNeedSwap = true;
int parentIndex = 0;
while (index != 1 && isNeedSwap) {
parentIndex = index / 2;
if (datas[index] < datas[parentIndex])
{
//小于父节点
int temp = datas[parentIndex];
datas[parentIndex] = datas[index];
datas[index] = temp;
}
else {
isNeedSwap = false;
}
index = parentIndex;
}
}
}主要的方法：
最小堆的创建，Create()方法，找到后数上来的第一个非叶节点，然后依次往上执行向下调整，这样就可以减少对叶节点调整的无用操作了。
向上调整，就是跟父节点对比，如果要调整，就交换位置，继续在父节点位置上对比父父节点，直到不需要调整或则到根节点为止
向下调整，同样的，不过向下调整要对比两个子节点，那么就是对比当前3个的最值，根据对比出来的值做出调整，然后继续向下调整，直到自己就是最值了或则变成叶节点了。
最小堆和最大堆是一种完全二叉树。每一个父节点都比它的左右儿子节点要小，这就是最小堆。相反的，每一个父节点都比它左右儿子节点要大，这就是最大堆。
满二叉树就是深度为h的数一定有 2h-1 个节点，不缺失任何一个节点。
完全二叉树就是满二叉树从右往左顺序少了一个到多个叶节点，注意是叶节点，叶节点以上的层次要完整，最下的叶节点层从左往右也要连续。
完全二叉树可以用一个线性的数组来存储：
如果一个父节点编号为k，那么左儿子为2*k，右孩子为2*k+1
父节点的编号就等于子节点的编号/2，向下取整数
树的高度=log2N ，N是节点的数量
最后一个非叶子节点为N/2