Looking for more information on how to do PHP the right way? Check out PHP: The Right Way

PHPMaster.com:
Data Structures for PHP Devs: Heaps
Jul 23, 2013 @ 11:10:17

PHPMaster.com has posted the third part of their "Data Structures for PHP Devs" series today, this time focusing on heaps. Heaps are a method for organizing a parent/child relationship that makes it easier to work with.

In past couple articles I’ve introduced you to three basic data structures: stack, queue, and tree. In this article I’ll introduce you to another abstract data type that is closely related: heap. Heaps are specialized tree-like data structures which satisfy the heap property – the node value (key) of any parent is always ordered with respect to its child node values across the entire tree.

He starts off by explaining what the different types of heaps are - maxheap, minheap and (a special instance) a Priority Queue. He talks about the operations available to heaps and starts off with a binary maxheap implementation using arrays. He also mentions some of the functionality that the SPL already provides for this sort of thing - SplMaxHeap, SplMinHeap and the SplPriorityQueue.

tagged: data structure heap tutorial series spl priority queue

Link: http://phpmaster.com/data-structures-3

Matthew Weier O'Phinney's Blog:
Taming SplPriorityQueue
Jan 18, 2011 @ 12:43:54

Matthew Weier O'Phinney has a new post to his blog today looking at one of the tools the Standard PHP Library (SPL) has to offer developers - the SplPriorityQueue (PHP 5.3+)

SplPriorityQueue is a fantastic new feature of PHP 5.3. However, in trying to utilize it in a few projects recently, I've run into some behavior that's (a) non-intuitive, and (b) in some cases at least, undesired. In this post, I'll present my solutions.

He talks about the "first in, first out" nature of queues and how it differs from a stack (including links to some of the other SPL offerings for both). He then moves into the problems he was seeing - that iteration removes values from the heap and the unexpected order of equal values in the queue. To solve the first problem, he creates an "outer iterator" that creates an "innerQueue" that's protected. The solution for the second issue - the random queue order - is a simple one: priority indexes aren't required to be integers. Strings can be substituted to help make things a bit more unique.

tagged: splpriorityqueue heap stack queue spl tutorial iterate priority index

Link:

Johannes Schluter's Blog:
Data structures in PHP 5.3
Dec 29, 2008 @ 11:19:28

Continuing on his his series looking at improvements in the upcoming PHP 5.3 release, Johannes Schluter uses this new post to look at some of the new data structures their update will have to offers in the Standard PHP Library.

In the programming world there are quite a few well understood and explored data structures. Which are commonly used in tons of applications, still the only things PHP offered till 5.3 in regards to structuring data were arrays (more precise: hash tables) and objects. So people had to either abuse them for other structures or implement the structures themselves on top of these. Thanks to Etienne things now are changing and PHP's Standard PHP Library (SPL) extension will offer quite a few standard implementations of data structures.

These new data structures are SplDoublyLinkedList, SplStack, SplQueue/SplPirorityQueue, SplHeap/SplMinHeap/SplMaxHeap and SplFixedArray. He explains a bit of what they are and more detail on one specifically - SplFixedArray.

tagged: data structure php5 spl standard library doublylinked stack queue heap fixedarray

Link:

Etienne Kneuss' Blog:
SPL Datastructures updated
May 13, 2008 @ 09:31:24

Etienne Kneuss has posted about some updates to the data structures functionality in the Standard PHP Library (SPL), specifically some new additions.

There finally is documentation for SplDoublyLinkedList, SplStack and SplQueue and some "new" classes: SplHeap (abstract), SplMaxHeap, SplMinHeap and SplPriorityQueue, documentation of those classes is in progress.

An example of the new functionality (for SplPriorityQueue) is included in the post showing the insertion of a value into a pre-existing array (without having to slice or splice!).

tagged: spl standardphplibrary datastructure heap priorityqueue

Link:

Hardened-PHP Project:
PHP HTML Entity Encoder Heap Overflow Vulnerability
Nov 03, 2006 @ 12:58:00

The Hardened-PHP Project has put out another advisory for the PHP distribution itself, versions 5.1.6/4.4.4 and below dealing with the HTML entity encoder heap.

While we were searching for a hole in htmlspecialchars() and htmlentities() to bypass the encoding of certain chars to exploit a possible eval() injection hole in another application we discovered that the implementation contains a possible bufferoverflow that can be triggered when the UTF-8 charset is selected.

The issue has been corrected in the latest PHP 5 release - version 5.2 - but is still present in the PHP 4.4 series (they have a recommended patch until the new version is posted). You can get complete information about this issue from the full vulnerability listing.

tagged: html entity encoded heap overflow vulnerability download update html entity encoded heap overflow vulnerability download update

Link:

Hardened-PHP Project:
PHP HTML Entity Encoder Heap Overflow Vulnerability
Nov 03, 2006 @ 12:58:00

The Hardened-PHP Project has put out another advisory for the PHP distribution itself, versions 5.1.6/4.4.4 and below dealing with the HTML entity encoder heap.

While we were searching for a hole in htmlspecialchars() and htmlentities() to bypass the encoding of certain chars to exploit a possible eval() injection hole in another application we discovered that the implementation contains a possible bufferoverflow that can be triggered when the UTF-8 charset is selected.

The issue has been corrected in the latest PHP 5 release - version 5.2 - but is still present in the PHP 4.4 series (they have a recommended patch until the new version is posted). You can get complete information about this issue from the full vulnerability listing.

tagged: html entity encoded heap overflow vulnerability download update html entity encoded heap overflow vulnerability download update

Link:

DevShed:
Collections and Sorting Continued
Apr 05, 2006 @ 07:13:17

Previously from DevShed, they started a series on collections and sorting in PHP. Today, they've posted part two of the series that builds on that and looks at sorting algorithm examples.

This article will examine the primary sorting algorithms with code examples, and some empirical data regarding how they perform in relation to one another, as well as the size of the data set in question.

We will also create a function to fill up our collection with random data in order to test the sort algorithms with a sufficiently large data set. The sort algorithms listed above are the ones that every computer science student learns in college and are the primary sort algorithms found in real-world applications.

The sorting styles they cover include: bubble sort, heap sort, merge sort, quick sort, and shell sort. For each, they provide the code, making it a simple matter of cut and paste to make it work in your script. There's not a whole lot of documentation going along with the code in this article, but the sorting code is simple enough to understand without it.

tagged: collections sorting bubble heap merge quick selection shell collections sorting bubble heap merge quick selection shell

Link:

DevShed:
Collections and Sorting Continued
Apr 05, 2006 @ 07:13:17

Previously from DevShed, they started a series on collections and sorting in PHP. Today, they've posted part two of the series that builds on that and looks at sorting algorithm examples.

This article will examine the primary sorting algorithms with code examples, and some empirical data regarding how they perform in relation to one another, as well as the size of the data set in question.

We will also create a function to fill up our collection with random data in order to test the sort algorithms with a sufficiently large data set. The sort algorithms listed above are the ones that every computer science student learns in college and are the primary sort algorithms found in real-world applications.

The sorting styles they cover include: bubble sort, heap sort, merge sort, quick sort, and shell sort. For each, they provide the code, making it a simple matter of cut and paste to make it work in your script. There's not a whole lot of documentation going along with the code in this article, but the sorting code is simple enough to understand without it.

tagged: collections sorting bubble heap merge quick selection shell collections sorting bubble heap merge quick selection shell

Link: