الگوریتم مبتنی بر Heap با سوئیفت — از صفر تا صد

1//a simple array of unsorted integers
2let numberList: Array<Int> = [8, 2, 10, 9, 11, 7]

1//formulas for heap indicies
2
3left = 2i + 1
4right = 2i + 2
5parent = floor(i - 1 / 2)

1...
2 
3    //construct the best path
4        var bestPath: Path = Path()        
5        
6        while frontier.count != 0 {
7            
8            //support path changes using the greedy approach
9            var pathIndex: Int = 0
10            
11            for x in 0..<frontier.count {
12               
13                let itemPath: Path = frontier[x]
14                
15                if  (bestPath.total == 0) || (itemPath.total < bestPath.total) {
16                    bestPath = itemPath
17                    pathIndex = x
18                }                
19            }
20...

1public class PathHeap {
2    
3    private var heap: Array<Path>
4    
5    init() {
6        heap = Array<Path>()
7    }
8        
9    //the number of frontier items
10    var count: Int {
11        return self.heap.count
12    }
13}

1//sort shortest paths into a min-heap (heapify)
2func enQueue(_ key: Path) {
3        
4        heap.append(key)
5            
6        var childIndex: Float = Float(heap.count) - 1
7        var parentIndex: Int = 0
8        
9        
10        //calculate parent index
11        if  childIndex != 0 {
12            parentIndex = Int(floorf((childIndex - 1) / 2))
13        }
14var childToUse: Path
15        var parentToUse: Path
16//use the bottom-up approach
17        while childIndex != 0 {            
18            
19            childToUse = heap[Int(childIndex)]
20            parentToUse = heap[parentIndex]
21            
22            
23            //swap child and parent positions
24            if childToUse.total < parentToUse.total {
25            heap.swapAt(parentIndex, Int(childIndex))
26            }
27                        
28            //reset indices
29            childIndex = Float(parentIndex)
30if childIndex != 0 {
31                parentIndex = Int(floorf((childIndex - 1) / 2))
32            }
33            
34            
35        } //end while
36        
37        
38    } //end function

1//obtain the minimum path
2func peek() -> Path? {
3        
4        if heap.count > 0 {
5           return heap[0]   //the shortest path
6        }
7        else {
8            return nil
9        }
10    }

1//a generic heap structure
2class Heap<T: Comparable> {
3        
4    private var items: Array<T>
5    private var heapType: HeapType
6        
7    //min-heap default initialization
8    init(type: HeapType = .Min) {
9        
10        items = Array<T>()
11        heapType = type
12    }
13       
14    
15    //the min or max value
16    func peek() -> T? {
17        
18        if items.count > 0 {
19            return items[0] //the min or max value
20        }
21        else {
22            return nil
23        }
24    }
25        
26    
27    //addition of new items
28    func enQueue(_ key: T) {
29        
30        items.append(key)        
31        
32        var childIndex: Float = Float(items.count) - 1
33        var parentIndex: Int = 0
34        
35        
36        //calculate parent index
37        if childIndex != 0 {
38            parentIndex = Int(floorf((childIndex - 1) / 2))
39        }
40        
41        
42        var childToUse: T
43        var parentToUse: T
44        
45        
46        //use the bottom-up approach
47        while childIndex != 0 {
48            
49            
50            childToUse = items[Int(childIndex)]
51            parentToUse = items[parentIndex]
52            
53            
54            //heapify depending on type
55            switch heapType {
56                
57            case .Min:
58                
59                //swap child and parent positions
60                if childToUse <= parentToUse {
61                    items.swapAt(parentIndex, Int(childIndex))
62                }
63                
64            case .Max:
65                
66                //swap child and parent positions
67                if childToUse >= parentToUse {
68                    items.swapAt(parentIndex, Int(childIndex))
69                }                
70            }
71                        
72            //reset indices
73            childIndex = Float(parentIndex)            
74            
75            if childIndex != 0 {
76                parentIndex = Int(floorf((childIndex - 1) / 2))
77            }
78                        
79        } //end while
80} //end function    
81}
82//used for generic heap data structure processing
83enum HeapType {
84    
85    case Min
86    case Max
87}