算法导论读书笔记
最近在读算法导论，第一次看时总是走马观花，缺少总结理解，最也搭上了博客于是就总结总结自己的理解~顺便锻炼下自己的写作能力。
堆的定义：可以视作一个完全二叉树，并且数的每一层都是的满的。其中有几个定义：
结点在树中的高度：是结点向下到某个叶结点的最长简单路径的边的条数
树的高度即为根的高度
堆的左右儿子的求法，可以将堆看作一个数组，下标从1开始，结点i的左右儿子分别为：left=2i；right=2i+1
- 在程序中其求法可采用位运算左移以及低位+1来实现。
堆的分类 * 最大堆：根结点的值最大，并且其每个结点都满足这个条件。 * 最小堆：根结点的值最小，并且每个结点都依次满足此条件。 * 堆的一些相关计算：
高度为h的堆中：最多的元素个数：全满的情况
最少元素个数：只含有一个叶结点的情况
* 含n个元素的堆的高度为通过最多最少的元素求
便可得。 * 当用数组表示存储了n个元素的堆时，叶子结点的下标为：
根据前两个性质，可以得出此堆的高度为即
保持堆的性质
即为保持最大堆或最小堆得性质。
* 保持最大堆：方法即为从一个给定的结点下标的父节点开始，与其儿子进行比较，若儿子大于其父结点则进行交换，交换后，有可能破坏其性质，则继续以此交换后的结点作为父节点进行迭代。
* 保持最小堆：方法与最大堆相同，不同的是比较方法相反。
* 时间复杂度的计算：以保持最大堆为例，作用在一个以结点i为根、大小为n的子树上：其中进行判断大小的时间复杂度为 然后考虑迭代过程的代价，最坏的情况是在最底层恰好半满的时候，即左子树或右子树达到最多的情况，其大小为
- 证明： 树的大小为n，设当左子树的size达到最大时，其中最底层半满，其个数为x ，设其高度为h 因此
即若此树为满树时叶子结点的个数
那么
即为次数为满树时结点的个数
根据假设可得到因此左子树的size为
/2)
可以得到- 网上的一个比较简单的解释为：一颗完全二叉树，最下层半满的时候，根节点的左子树节点数就是右子树的2倍，所以左子树节点数为2/3n
- 因此其时间复杂度为：
根据主方法可求得
建堆
先提出一个结论：
在任意高度h上，至多有个结点，其证明可参考：堆排序
建堆的方式即从底层的非叶子结点开始迭代调用保持最大堆的算法，其运行时间的界为
既可以在线性时间内建成一个最大（最小）堆。
堆排序
这个比较好理解，即首先先建堆，然后将其根结点与数组的最后一个元素互换，然后将数组待排序的size-1，然后不断的在根结点进行保持堆得算法运算，不断的将保持堆后的根结点放入数组的最后一个元素，最后即完成排序。其时间复杂度为
C++实现
1 #include "stdafx.h"
2 #include<assert.h>
3 #include <stdio.h>
4 #include<math.h>
5 class Heap
6 {
7 public:
8 // construction & dec
9 Heap(){};
10 ~Heap(){};
11 //method
12 bool init(int *pArray,int arraySize){
13 assert(pArray);
14 m_pArray = pArray;
15 m_iArraySize = arraySize;
16 return true;
17
18 };
19 // get index with shift heapsize = arraysize+1
20 const int parent(int iHeap_index) {return iHeap_index/2-1;};
21 const int left(int iHeap_index) {return 2*iHeap_index-1;};
22 const int right(int iHeap_index) {return 2*iHeap_index;};
23 // MAX-HEAPIFY(A,i)
24 void maxHeapify(int iHeap_index){
25 int largestIndex;
26 int iArray_index = iHeap_index-1;
27 int leftArrayIndex = left(iHeap_index);
28 int rightArrayIndex = right(iHeap_index);
29 if (leftArrayIndex<m_iArraySize&&m_pArray[leftArrayIndex]>m_pArray[iArray_index])
30 {
31 largestIndex = leftArrayIndex;
32 }else
33 largestIndex = iArray_index;
34 if (rightArrayIndex<m_iArraySize&&m_pArray[rightArrayIndex]>m_pArray[largestIndex])
35 {
36 largestIndex = rightArrayIndex;
37 }
38 if (largestIndex!=iArray_index)
39 {
40 int temp = m_pArray[iArray_index];
41 m_pArray[iArray_index] = m_pArray[largestIndex];
42 m_pArray[largestIndex] = temp;
43 maxHeapify(largestIndex+1);
44
45 }
46
47
48 };
49 // BUILD MAX HEAP
50 void buildMaxHeap(){
51 int istartNode = m_iArraySize/2;
52 for (int i = istartNode; i>0 ; i--)
53 {
54 maxHeapify(i);
55 }
56 };
57 // sort the heap
58 void heapSort(){
59 int itempSiez = m_iArraySize;
60 buildMaxHeap();
61 for (int i = m_iArraySize; i > 1; i--)
62 {
63 int temp = m_pArray[i-1];
64 m_pArray[i-1] = m_pArray[0];
65 m_pArray[0] = temp;
66 --m_iArraySize;
67 maxHeapify(1);
68
69
70 }
71 m_iArraySize=itempSiez;
72 };
73 // print
74 void printarray(){
75 for (int i = 0; i < m_iArraySize; i++)
76 {
77 printf("%d\n",m_pArray[i]);
78
79 }
80 };
81
82
83 private:
84 int* m_pArray;
85 int m_iArraySize;
86 };
87
88
89 int _tmain(int argc, _TCHAR* argv[])
90 {
91 //int a[]={16,4,10,14,7,9,3,2,8,1};
92 int a[]={4,1,3,2,16,9,10,14,8,7,7};
93 Heap heapp;
94 if(heapp.init(a,11))
95 {
96 //heapp.maxHeapify(2);
97 //heapp.buildMaxHeap();
98 heapp.heapSort();
99 heapp.printarray();
100 }
101
102 return 0;
103 }