PDF Publication Title:
Text from PDF Page: 151
6.4.1 A Matlab heap structure To implement both Dijkstra’s shortest path algorithm and Prim’s minimum spanning tree algorithm we need a means to store and access vertices, in sorted order, based on a constantly changing set of values. A heap is one data structure that meets these requirements [Cormen et al., 2001]. In this section, we discuss a Matlab implementation of a heap. The following implementation is inspired by Kahaner [1980].14 From a data structure perspective, a heap is a binary tree where smaller elements are parents of larger elements. It supports the following operations: 14 More generally speaking, algorithms written in Fortran 77 are excellent can- didates for the Matlab just-in-time compiler. The array 567196 corresponds to the following tree: 5 87 196 Figure 6.3 – Binary trees as arrays. 15 For items without natural ids, ids can be uniquely assigned based on how many items have already been added to the heap. In this case, D(i) contains the ith item added to the heap. 16 An alternative is to grow the heap by reallocating the arrays if additional items must be added. insert pop update add an element to the heap; remove the element from the heap with the smallest value; and change the value of an element in the heap. Matlab specializes in arrays (or vectors), and a common way to store a binary tree in an array is to associate the tree node of index j with a left child of index 2 j and a right child of index 2 j + 1. See figure 6.3 for an example. The data structure for our Matlab heap will consist of four arrays and one number. t the heap tree. The array T stores the identifiers of the items in the heap. That is, T(i) is the id of the element in tree node i and T(1) is the id of the element at the root of the heap tree. d the data store. The array T stores ids of elements in D so that D(T(i)) is the actual item for tree node i.15 The size of D must be the maximum number of items ever added to the heap.16 l a look up table. The size of L is the maximum id of any item added to the heap. For id i, L(i) is the tree node index of i in T, and T(L(i)) = i. v the value array. The current value associated with id i is given by V(i). This means that D(i) and V(i) are the item and its value, respectively. n thecurrentsizeoftheheap. When we use this heap structure to store vertices of a graph, there is no need to maintain the data array D. Each vertex is just a unique numeric identifier for the compressed sparse row arrays that gaimc uses. With D, T(⋅) contains the index of an element in D. When we store vertices in the heap, each vertex already has a unique identifier—its index—and the array D is unnecessary. 6.4 ⋅ gaimc 131PDF Image | MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITY
PDF Search Title:
MODELS AND ALGORITHMS FOR PAGERANK SENSITIVITYOriginal File Name Searched:
gleich-pagerank-thesis.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
| CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com | RSS | AMP |